001/*
002 * (C) Copyright 2014 Nuxeo SA (http://nuxeo.com/) and contributors.
003 *
004 * All rights reserved. This program and the accompanying materials
005 * are made available under the terms of the GNU Lesser General Public License
006 * (LGPL) version 2.1 which accompanies this distribution, and is available at
007 * http://www.gnu.org/licenses/lgpl-2.1.html
008 *
009 * This library is distributed in the hope that it will be useful,
010 * but WITHOUT ANY WARRANTY; without even the implied warranty of
011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012 * Lesser General Public License for more details.
013 *
014 * Contributors:
015 *     Florent Guillaume
016 */
017package org.nuxeo.ecm.core.storage.mongodb;
018
019import static java.lang.Boolean.FALSE;
020import static java.lang.Boolean.TRUE;
021import static org.nuxeo.ecm.core.storage.dbs.DBSDocument.KEY_ACE_GRANT;
022import static org.nuxeo.ecm.core.storage.dbs.DBSDocument.KEY_ACL;
023import static org.nuxeo.ecm.core.storage.dbs.DBSDocument.KEY_ACL_NAME;
024import static org.nuxeo.ecm.core.storage.dbs.DBSDocument.KEY_ACP;
025import static org.nuxeo.ecm.core.storage.dbs.DBSDocument.KEY_FULLTEXT_SCORE;
026import static org.nuxeo.ecm.core.storage.dbs.DBSDocument.KEY_ID;
027import static org.nuxeo.ecm.core.storage.dbs.DBSDocument.KEY_NAME;
028import static org.nuxeo.ecm.core.storage.dbs.DBSDocument.KEY_PARENT_ID;
029import static org.nuxeo.ecm.core.storage.mongodb.MongoDBRepository.MONGODB_ID;
030import static org.nuxeo.ecm.core.storage.mongodb.MongoDBRepository.MONGODB_META;
031import static org.nuxeo.ecm.core.storage.mongodb.MongoDBRepository.MONGODB_TEXT_SCORE;
032
033import java.util.ArrayList;
034import java.util.Arrays;
035import java.util.Collections;
036import java.util.Date;
037import java.util.HashMap;
038import java.util.HashSet;
039import java.util.Iterator;
040import java.util.LinkedHashMap;
041import java.util.LinkedList;
042import java.util.List;
043import java.util.Map;
044import java.util.Map.Entry;
045import java.util.Set;
046import java.util.concurrent.atomic.AtomicInteger;
047import java.util.regex.Matcher;
048import java.util.regex.Pattern;
049
050import org.apache.commons.lang.StringUtils;
051import org.apache.commons.lang.math.NumberUtils;
052import org.nuxeo.ecm.core.query.QueryParseException;
053import org.nuxeo.ecm.core.query.sql.NXQL;
054import org.nuxeo.ecm.core.query.sql.model.BooleanLiteral;
055import org.nuxeo.ecm.core.query.sql.model.DateLiteral;
056import org.nuxeo.ecm.core.query.sql.model.DoubleLiteral;
057import org.nuxeo.ecm.core.query.sql.model.Expression;
058import org.nuxeo.ecm.core.query.sql.model.Function;
059import org.nuxeo.ecm.core.query.sql.model.IntegerLiteral;
060import org.nuxeo.ecm.core.query.sql.model.Literal;
061import org.nuxeo.ecm.core.query.sql.model.LiteralList;
062import org.nuxeo.ecm.core.query.sql.model.MultiExpression;
063import org.nuxeo.ecm.core.query.sql.model.Operand;
064import org.nuxeo.ecm.core.query.sql.model.Operator;
065import org.nuxeo.ecm.core.query.sql.model.OrderByClause;
066import org.nuxeo.ecm.core.query.sql.model.OrderByExpr;
067import org.nuxeo.ecm.core.query.sql.model.Reference;
068import org.nuxeo.ecm.core.query.sql.model.SelectClause;
069import org.nuxeo.ecm.core.query.sql.model.SelectList;
070import org.nuxeo.ecm.core.query.sql.model.StringLiteral;
071import org.nuxeo.ecm.core.schema.DocumentType;
072import org.nuxeo.ecm.core.schema.SchemaManager;
073import org.nuxeo.ecm.core.schema.types.Field;
074import org.nuxeo.ecm.core.schema.types.ListType;
075import org.nuxeo.ecm.core.schema.types.Schema;
076import org.nuxeo.ecm.core.schema.types.Type;
077import org.nuxeo.ecm.core.schema.types.primitives.BooleanType;
078import org.nuxeo.ecm.core.storage.ExpressionEvaluator;
079import org.nuxeo.ecm.core.storage.ExpressionEvaluator.PathResolver;
080import org.nuxeo.ecm.core.storage.dbs.DBSDocument;
081import org.nuxeo.ecm.core.storage.dbs.DBSSession;
082import org.nuxeo.ecm.core.storage.FulltextQueryAnalyzer;
083import org.nuxeo.ecm.core.storage.FulltextQueryAnalyzer.FulltextQuery;
084import org.nuxeo.ecm.core.storage.FulltextQueryAnalyzer.Op;
085import org.nuxeo.runtime.api.Framework;
086
087import com.mongodb.BasicDBObject;
088import com.mongodb.DBObject;
089import com.mongodb.QueryOperators;
090
091/**
092 * Query builder for a MongoDB query from an {@link Expression}.
093 *
094 * @since 5.9.4
095 */
096public class MongoDBQueryBuilder {
097
098    private static final Long ZERO = Long.valueOf(0);
099
100    private static final Long ONE = Long.valueOf(1);
101
102    private static final Long MINUS_ONE = Long.valueOf(-1);
103
104    protected final AtomicInteger counter = new AtomicInteger();
105
106    protected final SchemaManager schemaManager;
107
108    protected List<String> documentTypes;
109
110    protected final Expression expression;
111
112    protected final SelectClause selectClause;
113
114    protected final OrderByClause orderByClause;
115
116    protected final PathResolver pathResolver;
117
118    public boolean hasFulltext;
119
120    public boolean sortOnFulltextScore;
121
122    protected DBObject query;
123
124    protected DBObject orderBy;
125
126    protected DBObject projection;
127
128    public MongoDBQueryBuilder(Expression expression, SelectClause selectClause, OrderByClause orderByClause,
129            PathResolver pathResolver) {
130        schemaManager = Framework.getLocalService(SchemaManager.class);
131        this.expression = expression;
132        this.selectClause = selectClause;
133        this.orderByClause = orderByClause;
134        this.pathResolver = pathResolver;
135    }
136
137    public void walk() {
138        query = walkExpression(expression); // computes hasFulltext
139        walkOrderBy(); // computes sortOnFulltextScore
140        walkProjection(); // needs hasFulltext and sortOnFulltextScore
141    }
142
143    public DBObject getQuery() {
144        return query;
145    }
146
147    public DBObject getOrderBy() {
148        return orderBy;
149    }
150
151    public DBObject getProjection() {
152        return projection;
153    }
154
155    protected void walkOrderBy() {
156        sortOnFulltextScore = false;
157        if (orderByClause == null) {
158            orderBy = null;
159        } else {
160            orderBy = new BasicDBObject();
161            for (OrderByExpr ob : orderByClause.elements) {
162                Reference ref = ob.reference;
163                boolean desc = ob.isDescending;
164                String field = walkReference(ref).queryField;
165                if (!orderBy.containsField(field)) {
166                    Object value;
167                    if (KEY_FULLTEXT_SCORE.equals(field)) {
168                        if (!desc) {
169                            throw new QueryParseException("Cannot sort by " + NXQL.ECM_FULLTEXT_SCORE + " ascending");
170                        }
171                        sortOnFulltextScore = true;
172                        value = new BasicDBObject(MONGODB_META, MONGODB_TEXT_SCORE);
173                    } else {
174                        value = desc ? MINUS_ONE : ONE;
175                    }
176                    orderBy.put(field, value);
177                }
178            }
179            if (sortOnFulltextScore && ((BasicDBObject) orderBy).size() > 1) {
180                throw new QueryParseException("Cannot sort by " + NXQL.ECM_FULLTEXT_SCORE + " and other criteria");
181            }
182        }
183    }
184
185    protected void walkProjection() {
186        if (selectClause.isEmpty()) {
187            selectClause.add(new Reference(NXQL.ECM_UUID));
188        }
189        SelectList elements = selectClause.elements;
190        projection = new BasicDBObject();
191        projection.put(KEY_ID, ONE); // always useful
192        projection.put(KEY_NAME, ONE); // used in order by path
193        projection.put(KEY_PARENT_ID, ONE); // used in order by path
194        boolean projectionHasWildcard = false;
195        boolean projectionOnFulltextScore = false;
196        for (int i = 0; i < elements.size(); i++) {
197            Operand op = elements.get(i);
198            if (!(op instanceof Reference)) {
199                throw new QueryParseException("Projection not supported: " + op);
200            }
201            FieldInfo fieldInfo = walkReference((Reference) op);
202            projection.put(fieldInfo.projectionField, ONE);
203            if (fieldInfo.hasWildcard) {
204                projectionHasWildcard = true;
205            }
206            if (fieldInfo.projectionField.equals(KEY_FULLTEXT_SCORE)) {
207                projectionOnFulltextScore = true;
208            }
209        }
210        if (projectionOnFulltextScore || sortOnFulltextScore) {
211            if (!hasFulltext) {
212                throw new QueryParseException(NXQL.ECM_FULLTEXT_SCORE + " cannot be used without " + NXQL.ECM_FULLTEXT);
213            }
214            projection.put(KEY_FULLTEXT_SCORE, new BasicDBObject(MONGODB_META, MONGODB_TEXT_SCORE));
215        }
216    }
217
218    public DBObject walkExpression(Expression expr) {
219        Operator op = expr.operator;
220        Operand lvalue = expr.lvalue;
221        Operand rvalue = expr.rvalue;
222        String name = lvalue instanceof Reference ? ((Reference) lvalue).name : null;
223        if (op == Operator.STARTSWITH) {
224            return walkStartsWith(lvalue, rvalue);
225        } else if (NXQL.ECM_PATH.equals(name)) {
226            return walkEcmPath(op, rvalue);
227        } else if (NXQL.ECM_ANCESTORID.equals(name)) {
228            return walkAncestorId(op, rvalue);
229        } else if (name != null && name.startsWith(NXQL.ECM_FULLTEXT) && !NXQL.ECM_FULLTEXT_JOBID.equals(name)) {
230            return walkEcmFulltext(name, op, rvalue);
231        } else if (op == Operator.SUM) {
232            throw new UnsupportedOperationException("SUM");
233        } else if (op == Operator.SUB) {
234            throw new UnsupportedOperationException("SUB");
235        } else if (op == Operator.MUL) {
236            throw new UnsupportedOperationException("MUL");
237        } else if (op == Operator.DIV) {
238            throw new UnsupportedOperationException("DIV");
239        } else if (op == Operator.LT) {
240            return walkLt(lvalue, rvalue);
241        } else if (op == Operator.GT) {
242            return walkGt(lvalue, rvalue);
243        } else if (op == Operator.EQ) {
244            return walkEq(lvalue, rvalue);
245        } else if (op == Operator.NOTEQ) {
246            return walkNotEq(lvalue, rvalue);
247        } else if (op == Operator.LTEQ) {
248            return walkLtEq(lvalue, rvalue);
249        } else if (op == Operator.GTEQ) {
250            return walkGtEq(lvalue, rvalue);
251        } else if (op == Operator.AND) {
252            if (expr instanceof MultiExpression) {
253                return walkMultiExpression((MultiExpression) expr);
254            } else {
255                return walkAnd(lvalue, rvalue);
256            }
257        } else if (op == Operator.NOT) {
258            return walkNot(lvalue);
259        } else if (op == Operator.OR) {
260            return walkOr(lvalue, rvalue);
261        } else if (op == Operator.LIKE) {
262            return walkLike(lvalue, rvalue, true, false);
263        } else if (op == Operator.ILIKE) {
264            return walkLike(lvalue, rvalue, true, true);
265        } else if (op == Operator.NOTLIKE) {
266            return walkLike(lvalue, rvalue, false, false);
267        } else if (op == Operator.NOTILIKE) {
268            return walkLike(lvalue, rvalue, false, true);
269        } else if (op == Operator.IN) {
270            return walkIn(lvalue, rvalue, true);
271        } else if (op == Operator.NOTIN) {
272            return walkIn(lvalue, rvalue, false);
273        } else if (op == Operator.ISNULL) {
274            return walkIsNull(lvalue);
275        } else if (op == Operator.ISNOTNULL) {
276            return walkIsNotNull(lvalue);
277        } else if (op == Operator.BETWEEN) {
278            return walkBetween(lvalue, rvalue, true);
279        } else if (op == Operator.NOTBETWEEN) {
280            return walkBetween(lvalue, rvalue, false);
281        } else {
282            throw new QueryParseException("Unknown operator: " + op);
283        }
284    }
285
286    protected DBObject walkEcmPath(Operator op, Operand rvalue) {
287        if (op != Operator.EQ && op != Operator.NOTEQ) {
288            throw new QueryParseException(NXQL.ECM_PATH + " requires = or <> operator");
289        }
290        if (!(rvalue instanceof StringLiteral)) {
291            throw new QueryParseException(NXQL.ECM_PATH + " requires literal path as right argument");
292        }
293        String path = ((StringLiteral) rvalue).value;
294        if (path.length() > 1 && path.endsWith("/")) {
295            path = path.substring(0, path.length() - 1);
296        }
297        String id = pathResolver.getIdForPath(path);
298        if (id == null) {
299            // no such path
300            // TODO XXX do better
301            return new BasicDBObject(MONGODB_ID, "__nosuchid__");
302        }
303        if (op == Operator.EQ) {
304            return new BasicDBObject(DBSDocument.KEY_ID, id);
305        } else {
306            return new BasicDBObject(DBSDocument.KEY_ID, new BasicDBObject(QueryOperators.NE, id));
307        }
308    }
309
310    protected DBObject walkAncestorId(Operator op, Operand rvalue) {
311        if (op != Operator.EQ && op != Operator.NOTEQ) {
312            throw new QueryParseException(NXQL.ECM_ANCESTORID + " requires = or <> operator");
313        }
314        if (!(rvalue instanceof StringLiteral)) {
315            throw new QueryParseException(NXQL.ECM_ANCESTORID + " requires literal id as right argument");
316        }
317        String ancestorId = ((StringLiteral) rvalue).value;
318        if (op == Operator.EQ) {
319            return new BasicDBObject(DBSDocument.KEY_ANCESTOR_IDS, ancestorId);
320        } else {
321            return new BasicDBObject(DBSDocument.KEY_ANCESTOR_IDS, new BasicDBObject(QueryOperators.NE, ancestorId));
322        }
323    }
324
325    protected DBObject walkEcmFulltext(String name, Operator op, Operand rvalue) {
326        if (op != Operator.EQ && op != Operator.LIKE) {
327            throw new QueryParseException(NXQL.ECM_FULLTEXT + " requires = or LIKE operator");
328        }
329        if (!(rvalue instanceof StringLiteral)) {
330            throw new QueryParseException(NXQL.ECM_FULLTEXT + " requires literal string as right argument");
331        }
332        String fulltextQuery = ((StringLiteral) rvalue).value;
333        if (name.equals(NXQL.ECM_FULLTEXT)) {
334            // standard fulltext query
335            hasFulltext = true;
336            String ft = getMongoDBFulltextQuery(fulltextQuery);
337            if (ft == null) {
338                // empty query, matches nothing
339                return new BasicDBObject(MONGODB_ID, "__nosuchid__");
340            }
341            DBObject textSearch = new BasicDBObject();
342            textSearch.put(QueryOperators.SEARCH, ft);
343            // TODO language?
344            return new BasicDBObject(QueryOperators.TEXT, textSearch);
345        } else {
346            // secondary index match with explicit field
347            // do a regexp on the field
348            if (name.charAt(NXQL.ECM_FULLTEXT.length()) != '.') {
349                throw new QueryParseException(name + " has incorrect syntax" + " for a secondary fulltext index");
350            }
351            String prop = name.substring(NXQL.ECM_FULLTEXT.length() + 1);
352            String ft = fulltextQuery.replace(" ", "%");
353            rvalue = new StringLiteral(ft);
354            return walkLike(new Reference(prop), rvalue, true, true);
355        }
356    }
357
358    // public static for tests
359    public static String getMongoDBFulltextQuery(String query) {
360        FulltextQuery ft = FulltextQueryAnalyzer.analyzeFulltextQuery(query);
361        if (ft == null) {
362            return null;
363        }
364        // translate into MongoDB syntax
365        return translateFulltext(ft, false);
366    }
367
368    /**
369     * Transforms the NXQL fulltext syntax into MongoDB syntax.
370     * <p>
371     * The MongoDB fulltext query syntax is badly documented, but is actually the following:
372     * <ul>
373     * <li>a term is a word,
374     * <li>a phrase is a set of spaced-separated words enclosed in double quotes,
375     * <li>negation is done by prepending a -,
376     * <li>the query is a space-separated set of terms, negated terms, phrases, or negated phrases.
377     * <li>all the words of non-negated phrases are also added to the terms.
378     * </ul>
379     * <p>
380     * The matching algorithm is (excluding stemming and stop words):
381     * <ul>
382     * <li>filter out documents with the negative terms, the negative phrases, or missing the phrases,
383     * <li>then if any term is present in the document then it's a match.
384     * </ul>
385     */
386    protected static String translateFulltext(FulltextQuery ft, boolean and) {
387        List<String> buf = new ArrayList<>();
388        translateFulltext(ft, buf, and);
389        return StringUtils.join(buf, ' ');
390    }
391
392    protected static void translateFulltext(FulltextQuery ft, List<String> buf, boolean and) {
393        if (ft.op == Op.OR) {
394            for (FulltextQuery term : ft.terms) {
395                // don't quote words for OR
396                translateFulltext(term, buf, false);
397            }
398        } else if (ft.op == Op.AND) {
399            for (FulltextQuery term : ft.terms) {
400                // quote words for AND
401                translateFulltext(term, buf, true);
402            }
403        } else {
404            String neg;
405            if (ft.op == Op.NOTWORD) {
406                neg = "-";
407            } else { // Op.WORD
408                neg = "";
409            }
410            String word = ft.word.toLowerCase();
411            if (ft.isPhrase() || and) {
412                buf.add(neg + '"' + word + '"');
413            } else {
414                buf.add(neg + word);
415            }
416        }
417    }
418
419    public DBObject walkNot(Operand value) {
420        Object val = walkOperand(value);
421        Object not = pushDownNot(val);
422        if (!(not instanceof DBObject)) {
423            throw new QueryParseException("Cannot do NOT on: " + val);
424        }
425        return (DBObject) not;
426    }
427
428    protected Object pushDownNot(Object object) {
429        if (!(object instanceof DBObject)) {
430            throw new QueryParseException("Cannot do NOT on: " + object);
431        }
432        DBObject ob = (DBObject) object;
433        Set<String> keySet = ob.keySet();
434        if (keySet.size() != 1) {
435            throw new QueryParseException("Cannot do NOT on: " + ob);
436        }
437        String key = keySet.iterator().next();
438        Object value = ob.get(key);
439        if (!key.startsWith("$")) {
440            if (value instanceof DBObject) {
441                // push down inside dbobject
442                return new BasicDBObject(key, pushDownNot(value));
443            } else {
444                // k = v -> k != v
445                return new BasicDBObject(key, new BasicDBObject(QueryOperators.NE, value));
446            }
447        }
448        if (QueryOperators.NE.equals(key)) {
449            // NOT k != v -> k = v
450            return value;
451        }
452        if (QueryOperators.NOT.equals(key)) {
453            // NOT NOT v -> v
454            return value;
455        }
456        if (QueryOperators.AND.equals(key) || QueryOperators.OR.equals(key)) {
457            // boolean algebra
458            // NOT (v1 AND v2) -> NOT v1 OR NOT v2
459            // NOT (v1 OR v2) -> NOT v1 AND NOT v2
460            String op = QueryOperators.AND.equals(key) ? QueryOperators.OR : QueryOperators.AND;
461            List<Object> list = (List<Object>) value;
462            for (int i = 0; i < list.size(); i++) {
463                list.set(i, pushDownNot(list.get(i)));
464            }
465            return new BasicDBObject(op, list);
466        }
467        if (QueryOperators.IN.equals(key) || QueryOperators.NIN.equals(key)) {
468            // boolean algebra
469            // IN <-> NIN
470            String op = QueryOperators.IN.equals(key) ? QueryOperators.NIN : QueryOperators.IN;
471            return new BasicDBObject(op, value);
472        }
473        if (QueryOperators.LT.equals(key) || QueryOperators.GT.equals(key) || QueryOperators.LTE.equals(key)
474                || QueryOperators.GTE.equals(key)) {
475            // TODO use inverse operators?
476            return new BasicDBObject(QueryOperators.NOT, ob);
477        }
478        throw new QueryParseException("Unknown operator for NOT: " + key);
479    }
480
481    public DBObject walkIsNull(Operand value) {
482        FieldInfo fieldInfo = walkReference(value);
483        return new FieldInfoDBObject(fieldInfo, null);
484    }
485
486    public DBObject walkIsNotNull(Operand value) {
487        FieldInfo fieldInfo = walkReference(value);
488        return new FieldInfoDBObject(fieldInfo, new BasicDBObject(QueryOperators.NE, null));
489    }
490
491    public DBObject walkMultiExpression(MultiExpression expr) {
492        return walkAnd(expr.values);
493    }
494
495    public DBObject walkAnd(Operand lvalue, Operand rvalue) {
496        return walkAnd(Arrays.asList(lvalue, rvalue));
497    }
498
499    protected DBObject walkAnd(List<Operand> values) {
500        List<Object> list = walkOperandList(values);
501        // check wildcards in the operands, extract common prefixes to use $elemMatch
502        Map<String, List<FieldInfoDBObject>> propBaseKeyToDBOs = new LinkedHashMap<>();
503        Map<String, String> propBaseKeyToFieldBase = new HashMap<>();
504        for (Iterator<Object> it = list.iterator(); it.hasNext();) {
505            Object ob = it.next();
506            if (ob instanceof FieldInfoDBObject) {
507                FieldInfoDBObject fidbo = (FieldInfoDBObject) ob;
508                FieldInfo fieldInfo = fidbo.fieldInfo;
509                if (fieldInfo.hasWildcard) {
510                    if (fieldInfo.fieldSuffix.contains("*")) {
511                        throw new QueryParseException("Cannot use two wildcards: " + fieldInfo.prop);
512                    }
513                    // generate a key unique per correlation for this element match
514                    String wildcardNumber = fieldInfo.fieldWildcard;
515                    if (wildcardNumber.isEmpty()) {
516                        // negative to not collide with regular correlated wildcards
517                        wildcardNumber = String.valueOf(-counter.incrementAndGet());
518                    }
519                    String propBaseKey = fieldInfo.fieldPrefix + "/*" + wildcardNumber;
520                    // store object for this key
521                    List<FieldInfoDBObject> dbos = propBaseKeyToDBOs.get(propBaseKey);
522                    if (dbos == null) {
523                        propBaseKeyToDBOs.put(propBaseKey, dbos = new LinkedList<>());
524                    }
525                    dbos.add(fidbo);
526                    // remember for which field base this is
527                    String fieldBase = fieldInfo.fieldPrefix.replace("/", ".");
528                    propBaseKeyToFieldBase.put(propBaseKey, fieldBase);
529                    // remove from list, will be re-added later through propBaseKeyToDBOs
530                    it.remove();
531                }
532            }
533        }
534        // generate $elemMatch items for correlated queries
535        for (Entry<String, List<FieldInfoDBObject>> es : propBaseKeyToDBOs.entrySet()) {
536            String propBaseKey = es.getKey();
537            List<FieldInfoDBObject> fidbos = es.getValue();
538            if (fidbos.size() == 1) {
539                // regular uncorrelated match
540                list.addAll(fidbos);
541            } else {
542                DBObject elemMatch = new BasicDBObject();
543                for (FieldInfoDBObject fidbo : fidbos) {
544                    // truncate field name to just the suffix
545                    FieldInfo fieldInfo = fidbo.fieldInfo;
546                    Object value = fidbo.get(fieldInfo.queryField);
547                    String fieldSuffix = fieldInfo.fieldSuffix.replace("/", ".");
548                    if (elemMatch.containsField(fieldSuffix)) {
549                        // ecm:acl/*1/principal = 'bob' AND ecm:acl/*1/principal = 'steve'
550                        // cannot match
551                        // TODO do better
552                        value = "__NOSUCHVALUE__";
553                    }
554                    elemMatch.put(fieldSuffix, value);
555                }
556                String fieldBase = propBaseKeyToFieldBase.get(propBaseKey);
557                BasicDBObject dbo = new BasicDBObject(fieldBase,
558                        new BasicDBObject(QueryOperators.ELEM_MATCH, elemMatch));
559                list.add(dbo);
560            }
561        }
562        if (list.size() == 1) {
563            return (DBObject) list.get(0);
564        } else {
565            return new BasicDBObject(QueryOperators.AND, list);
566        }
567    }
568
569    public DBObject walkOr(Operand lvalue, Operand rvalue) {
570        Object left = walkOperand(lvalue);
571        Object right = walkOperand(rvalue);
572        List<Object> list = new ArrayList<>(Arrays.asList(left, right));
573        return new BasicDBObject(QueryOperators.OR, list);
574    }
575
576    protected Object checkBoolean(FieldInfo fieldInfo, Object right) {
577        if (fieldInfo.isBoolean) {
578            // convert 0 / 1 to actual booleans
579            if (right instanceof Long) {
580                if (ZERO.equals(right)) {
581                    right = fieldInfo.isTrueOrNullBoolean ? null : FALSE;
582                } else if (ONE.equals(right)) {
583                    right = TRUE;
584                } else {
585                    throw new QueryParseException("Invalid boolean: " + right);
586                }
587            }
588        }
589        return right;
590    }
591
592    public DBObject walkEq(Operand lvalue, Operand rvalue) {
593        FieldInfo fieldInfo = walkReference(lvalue);
594        Object right = walkOperand(rvalue);
595        if (isMixinTypes(fieldInfo)) {
596            if (!(right instanceof String)) {
597                throw new QueryParseException("Invalid EQ rhs: " + rvalue);
598            }
599            return walkMixinTypes(Collections.singletonList((String) right), true);
600        }
601        right = checkBoolean(fieldInfo, right);
602        // TODO check list fields
603        return new FieldInfoDBObject(fieldInfo, right);
604    }
605
606    public DBObject walkNotEq(Operand lvalue, Operand rvalue) {
607        FieldInfo fieldInfo = walkReference(lvalue);
608        Object right = walkOperand(rvalue);
609        if (isMixinTypes(fieldInfo)) {
610            if (!(right instanceof String)) {
611                throw new QueryParseException("Invalid NE rhs: " + rvalue);
612            }
613            return walkMixinTypes(Collections.singletonList((String) right), false);
614        }
615        right = checkBoolean(fieldInfo, right);
616        // TODO check list fields
617        return new FieldInfoDBObject(fieldInfo, new BasicDBObject(QueryOperators.NE, right));
618    }
619
620    public DBObject walkLt(Operand lvalue, Operand rvalue) {
621        FieldInfo fieldInfo = walkReference(lvalue);
622        Object right = walkOperand(rvalue);
623        return new FieldInfoDBObject(fieldInfo, new BasicDBObject(QueryOperators.LT, right));
624    }
625
626    public DBObject walkGt(Operand lvalue, Operand rvalue) {
627        FieldInfo fieldInfo = walkReference(lvalue);
628        Object right = walkOperand(rvalue);
629        return new FieldInfoDBObject(fieldInfo, new BasicDBObject(QueryOperators.GT, right));
630    }
631
632    public DBObject walkLtEq(Operand lvalue, Operand rvalue) {
633        FieldInfo fieldInfo = walkReference(lvalue);
634        Object right = walkOperand(rvalue);
635        return new FieldInfoDBObject(fieldInfo, new BasicDBObject(QueryOperators.LTE, right));
636    }
637
638    public DBObject walkGtEq(Operand lvalue, Operand rvalue) {
639        FieldInfo fieldInfo = walkReference(lvalue);
640        Object right = walkOperand(rvalue);
641        return new FieldInfoDBObject(fieldInfo, new BasicDBObject(QueryOperators.GTE, right));
642    }
643
644    public DBObject walkBetween(Operand lvalue, Operand rvalue, boolean positive) {
645        LiteralList l = (LiteralList) rvalue;
646        FieldInfo fieldInfo = walkReference(lvalue);
647        Object left = walkOperand(l.get(0));
648        Object right = walkOperand(l.get(1));
649        if (positive) {
650            DBObject range = new BasicDBObject();
651            range.put(QueryOperators.GTE, left);
652            range.put(QueryOperators.LTE, right);
653            return new FieldInfoDBObject(fieldInfo, range);
654        } else {
655            DBObject a = new FieldInfoDBObject(fieldInfo, new BasicDBObject(QueryOperators.LT, left));
656            DBObject b = new FieldInfoDBObject(fieldInfo, new BasicDBObject(QueryOperators.GT, right));
657            return new BasicDBObject(QueryOperators.OR, Arrays.asList(a, b));
658        }
659    }
660
661    public DBObject walkIn(Operand lvalue, Operand rvalue, boolean positive) {
662        FieldInfo fieldInfo = walkReference(lvalue);
663        Object right = walkOperand(rvalue);
664        if (!(right instanceof List)) {
665            throw new QueryParseException("Invalid IN, right hand side must be a list: " + rvalue);
666        }
667        if (isMixinTypes(fieldInfo)) {
668            return walkMixinTypes((List<String>) right, positive);
669        }
670        // TODO check list fields
671        List<Object> list = (List<Object>) right;
672        return new FieldInfoDBObject(fieldInfo,
673                new BasicDBObject(positive ? QueryOperators.IN : QueryOperators.NIN, list));
674    }
675
676    public DBObject walkLike(Operand lvalue, Operand rvalue, boolean positive, boolean caseInsensitive) {
677        FieldInfo fieldInfo = walkReference(lvalue);
678        if (!(rvalue instanceof StringLiteral)) {
679            throw new QueryParseException("Invalid LIKE/ILIKE, right hand side must be a string: " + rvalue);
680        }
681        // TODO check list fields
682        String like = walkStringLiteral((StringLiteral) rvalue);
683        String regex = ExpressionEvaluator.likeToRegex(like);
684
685        int flags = caseInsensitive ? Pattern.CASE_INSENSITIVE : 0;
686        Pattern pattern = Pattern.compile(regex, flags);
687        Object value;
688        if (positive) {
689            value = pattern;
690        } else {
691            value = new BasicDBObject(QueryOperators.NOT, pattern);
692        }
693        return new FieldInfoDBObject(fieldInfo, value);
694    }
695
696    public Object walkOperand(Operand op) {
697        if (op instanceof Literal) {
698            return walkLiteral((Literal) op);
699        } else if (op instanceof LiteralList) {
700            return walkLiteralList((LiteralList) op);
701        } else if (op instanceof Function) {
702            return walkFunction((Function) op);
703        } else if (op instanceof Expression) {
704            return walkExpression((Expression) op);
705        } else if (op instanceof Reference) {
706            return walkReference((Reference) op);
707        } else {
708            throw new QueryParseException("Unknown operand: " + op);
709        }
710    }
711
712    public Object walkLiteral(Literal lit) {
713        if (lit instanceof BooleanLiteral) {
714            return walkBooleanLiteral((BooleanLiteral) lit);
715        } else if (lit instanceof DateLiteral) {
716            return walkDateLiteral((DateLiteral) lit);
717        } else if (lit instanceof DoubleLiteral) {
718            return walkDoubleLiteral((DoubleLiteral) lit);
719        } else if (lit instanceof IntegerLiteral) {
720            return walkIntegerLiteral((IntegerLiteral) lit);
721        } else if (lit instanceof StringLiteral) {
722            return walkStringLiteral((StringLiteral) lit);
723        } else {
724            throw new QueryParseException("Unknown literal: " + lit);
725        }
726    }
727
728    public Object walkBooleanLiteral(BooleanLiteral lit) {
729        return Boolean.valueOf(lit.value);
730    }
731
732    public Date walkDateLiteral(DateLiteral lit) {
733        return lit.value.toDate(); // TODO onlyDate
734    }
735
736    public Double walkDoubleLiteral(DoubleLiteral lit) {
737        return Double.valueOf(lit.value);
738    }
739
740    public Long walkIntegerLiteral(IntegerLiteral lit) {
741        return Long.valueOf(lit.value);
742    }
743
744    public String walkStringLiteral(StringLiteral lit) {
745        return lit.value;
746    }
747
748    public List<Object> walkLiteralList(LiteralList litList) {
749        List<Object> list = new ArrayList<Object>(litList.size());
750        for (Literal lit : litList) {
751            list.add(walkLiteral(lit));
752        }
753        return list;
754    }
755
756    protected List<Object> walkOperandList(List<Operand> values) {
757        List<Object> list = new LinkedList<>();
758        for (Operand value : values) {
759            list.add(walkOperand(value));
760        }
761        return list;
762    }
763
764    public Object walkFunction(Function func) {
765        throw new UnsupportedOperationException(func.name);
766    }
767
768    public DBObject walkStartsWith(Operand lvalue, Operand rvalue) {
769        if (!(lvalue instanceof Reference)) {
770            throw new QueryParseException("Invalid STARTSWITH query, left hand side must be a property: " + lvalue);
771        }
772        String name = ((Reference) lvalue).name;
773        if (!(rvalue instanceof StringLiteral)) {
774            throw new QueryParseException(
775                    "Invalid STARTSWITH query, right hand side must be a literal path: " + rvalue);
776        }
777        String path = ((StringLiteral) rvalue).value;
778        if (path.length() > 1 && path.endsWith("/")) {
779            path = path.substring(0, path.length() - 1);
780        }
781
782        if (NXQL.ECM_PATH.equals(name)) {
783            return walkStartsWithPath(path);
784        } else {
785            return walkStartsWithNonPath(lvalue, path);
786        }
787    }
788
789    protected DBObject walkStartsWithPath(String path) {
790        // resolve path
791        String ancestorId = pathResolver.getIdForPath(path);
792        if (ancestorId == null) {
793            // no such path
794            // TODO XXX do better
795            return new BasicDBObject(MONGODB_ID, "__nosuchid__");
796        }
797        return new BasicDBObject(DBSDocument.KEY_ANCESTOR_IDS, ancestorId);
798    }
799
800    protected DBObject walkStartsWithNonPath(Operand lvalue, String path) {
801        FieldInfo fieldInfo = walkReference(lvalue);
802        DBObject eq = new FieldInfoDBObject(fieldInfo, path);
803        // escape except alphanumeric and others not needing escaping
804        String regex = path.replaceAll("([^a-zA-Z0-9 /])", "\\\\$1");
805        Pattern pattern = Pattern.compile(regex + "/.*");
806        DBObject like = new FieldInfoDBObject(fieldInfo, pattern);
807        return new BasicDBObject(QueryOperators.OR, Arrays.asList(eq, like));
808    }
809
810    protected FieldInfo walkReference(Operand value) {
811        if (!(value instanceof Reference)) {
812            throw new QueryParseException("Invalid query, left hand side must be a property: " + value);
813        }
814        return walkReference((Reference) value);
815    }
816
817    // non-canonical index syntax, for replaceAll
818    protected final static Pattern NON_CANON_INDEX = Pattern.compile("[^/\\[\\]]+" // name
819            + "\\[(\\d+|\\*|\\*\\d+)\\]" // index in brackets
820    );
821
822    /**
823     * Canonicalizes a Nuxeo-xpath.
824     * <p>
825     * Replaces {@code a/foo[123]/b} with {@code a/123/b}
826     * <p>
827     * A star or a star followed by digits can be used instead of just the digits as well.
828     *
829     * @param xpath the xpath
830     * @return the canonicalized xpath.
831     */
832    public static String canonicalXPath(String xpath) {
833        while (xpath.length() > 0 && xpath.charAt(0) == '/') {
834            xpath = xpath.substring(1);
835        }
836        if (xpath.indexOf('[') == -1) {
837            return xpath;
838        } else {
839            return NON_CANON_INDEX.matcher(xpath).replaceAll("$1");
840        }
841    }
842
843    /** Splits foo.*.bar into foo, *, bar and foo.*1.bar into foo, *1, bar */
844    protected final static Pattern WILDCARD_SPLIT = Pattern.compile("([^*]*)\\.\\*(\\d*)\\.(.*)");
845
846    protected static class FieldInfo {
847
848        /** NXQL property. */
849        protected final String prop;
850
851        /** MongoDB field including wildcards (not used as-is). */
852        protected final String fullField;
853
854        /** MongoDB field for query. foo/0/bar -> foo.0.bar; foo / * / bar -> foo.bar */
855        protected final String queryField;
856
857        /** MongoDB field for projection. */
858        protected final String projectionField;
859
860        protected final boolean isBoolean;
861
862        /**
863         * Boolean system properties only use TRUE or NULL, not FALSE, so queries must be updated accordingly.
864         */
865        protected final boolean isTrueOrNullBoolean;
866
867        protected final boolean hasWildcard;
868
869        /** Prefix before the wildcard. */
870        protected final String fieldPrefix;
871
872        /** Wildcard part after * */
873        protected final String fieldWildcard;
874
875        /** Part after wildcard. */
876        protected final String fieldSuffix;
877
878        protected FieldInfo(String prop, String fullField, String queryField, String projectionField, boolean isBoolean,
879                boolean isTrueOrNullBoolean) {
880            this.prop = prop;
881            this.fullField = fullField;
882            this.queryField = queryField;
883            this.projectionField = projectionField;
884            this.isBoolean = isBoolean;
885            this.isTrueOrNullBoolean = isTrueOrNullBoolean;
886            Matcher m = WILDCARD_SPLIT.matcher(fullField);
887            if (m.matches()) {
888                hasWildcard = true;
889                fieldPrefix = m.group(1);
890                fieldWildcard = m.group(2);
891                fieldSuffix = m.group(3);
892            } else {
893                hasWildcard = false;
894                fieldPrefix = fieldWildcard = fieldSuffix = null;
895            }
896        }
897    }
898
899    protected static class FieldInfoDBObject extends BasicDBObject {
900
901        private static final long serialVersionUID = 1L;
902
903        protected FieldInfo fieldInfo;
904
905        public FieldInfoDBObject(FieldInfo fieldInfo, Object value) {
906            super(fieldInfo.queryField, value);
907            this.fieldInfo = fieldInfo;
908        }
909    }
910
911    /**
912     * Returns the MongoDB field for this reference.
913     */
914    public FieldInfo walkReference(Reference ref) {
915        String prop = ref.name;
916        prop = canonicalXPath(prop);
917        List<String> split = new LinkedList<>(Arrays.asList(StringUtils.split(prop, '/')));
918        if (prop.startsWith(NXQL.ECM_PREFIX)) {
919            if (prop.startsWith(NXQL.ECM_ACL + "/")) {
920                if (split.size() != 3) {
921                    throw new QueryParseException("No such property: " + ref.name);
922                }
923                String wildcard = split.get(1);
924                if (NumberUtils.isDigits(wildcard)) {
925                    throw new QueryParseException("Cannot use explicit index in ACLs: " + ref.name);
926                }
927                String last = split.get(2);
928                String fullField;
929                String queryField;
930                String projectionField;
931                boolean isBoolean;
932                if (NXQL.ECM_ACL_NAME.equals(last)) {
933                    fullField = KEY_ACP + "." + KEY_ACL_NAME;
934                    queryField = KEY_ACP + "." + KEY_ACL_NAME;
935                    // TODO remember wildcard correlation
936                    isBoolean = false;
937                } else {
938                    String fieldLast = DBSSession.convToInternalAce(last);
939                    if (fieldLast == null) {
940                        throw new QueryParseException("No such property: " + ref.name);
941                    }
942                    isBoolean = KEY_ACE_GRANT.equals(fieldLast);
943                    fullField = KEY_ACP + "." + KEY_ACL + "." + wildcard + "." + fieldLast;
944                    queryField = KEY_ACP + "." + KEY_ACL + "." + fieldLast;
945                }
946                projectionField = queryField;
947                return new FieldInfo(prop, fullField, queryField, projectionField, isBoolean, false);
948            } else {
949                // simple field
950                String field = DBSSession.convToInternal(prop);
951                boolean isBoolean = DBSSession.isBoolean(field);
952                return new FieldInfo(prop, field, field, field, isBoolean, true);
953            }
954        } else {
955            String first = split.get(0);
956            Field schemaField = schemaManager.getField(first);
957            if (schemaField == null) {
958                if (first.indexOf(':') > -1) {
959                    throw new QueryParseException("No such property: " + ref.name);
960                }
961                // check without prefix
962                // TODO precompute this in SchemaManagerImpl
963                for (Schema schema : schemaManager.getSchemas()) {
964                    if (!StringUtils.isBlank(schema.getNamespace().prefix)) {
965                        // schema with prefix, do not consider as candidate
966                        continue;
967                    }
968                    if (schema != null) {
969                        schemaField = schema.getField(first);
970                        if (schemaField != null) {
971                            break;
972                        }
973                    }
974                }
975                if (schemaField == null) {
976                    throw new QueryParseException("No such property: " + ref.name);
977                }
978            }
979            // canonical name
980            split.set(0, schemaField.getName().getPrefixedName());
981            prop = StringUtils.join(split, '/'); // canonicalized first component
982            // MongoDB embedded field syntax uses . separator
983            Type type = schemaField.getType();
984            boolean isArray = type instanceof ListType && ((ListType) type).isArray();
985            boolean isBoolean = type instanceof BooleanType;
986            // terminating wildcard for array -> just remove from query
987            if (isArray && split.get(split.size() - 1).startsWith("*")) {
988                // TODO correlations?
989                split.remove(split.size() - 1);
990            }
991            // are there wildcards or list indexes?
992            List<String> queryFieldParts = new LinkedList<>(); // field for query
993            List<String> projectionFieldParts = new LinkedList<>(); // field for projection
994            for (String part : split) {
995                if (!part.startsWith("*")) {
996                    queryFieldParts.add(part);
997                    if (!NumberUtils.isDigits(part)) {
998                        projectionFieldParts.add(part);
999                    }
1000                }
1001            }
1002            String fullField = StringUtils.join(split, '.');
1003            String queryField = StringUtils.join(queryFieldParts, '.');
1004            String projectionField = StringUtils.join(projectionFieldParts, '.');
1005            return new FieldInfo(prop, fullField, queryField, projectionField, isBoolean, false);
1006        }
1007    }
1008
1009    protected boolean isMixinTypes(FieldInfo fieldInfo) {
1010        return fieldInfo.queryField.equals(DBSDocument.KEY_MIXIN_TYPES);
1011    }
1012
1013    protected Set<String> getMixinDocumentTypes(String mixin) {
1014        Set<String> types = schemaManager.getDocumentTypeNamesForFacet(mixin);
1015        return types == null ? Collections.emptySet() : types;
1016    }
1017
1018    protected List<String> getDocumentTypes() {
1019        // TODO precompute in SchemaManager
1020        if (documentTypes == null) {
1021            documentTypes = new ArrayList<>();
1022            for (DocumentType docType : schemaManager.getDocumentTypes()) {
1023                documentTypes.add(docType.getName());
1024            }
1025        }
1026        return documentTypes;
1027    }
1028
1029    protected boolean isNeverPerInstanceMixin(String mixin) {
1030        return schemaManager.getNoPerDocumentQueryFacets().contains(mixin);
1031    }
1032
1033    /**
1034     * Matches the mixin types against a list of values.
1035     * <p>
1036     * Used for:
1037     * <ul>
1038     * <li>ecm:mixinTypes = 'Foo'
1039     * <li>ecm:mixinTypes != 'Foo'
1040     * <li>ecm:mixinTypes IN ('Foo', 'Bar')
1041     * <li>ecm:mixinTypes NOT IN ('Foo', 'Bar')
1042     * </ul>
1043     * <p>
1044     * ecm:mixinTypes IN ('Foo', 'Bar')
1045     *
1046     * <pre>
1047     * { "$or" : [ { "ecm:primaryType" : { "$in" : [ ... types with Foo or Bar ...]}} ,
1048     *             { "ecm:mixinTypes" : { "$in" : [ "Foo" , "Bar]}}]}
1049     * </pre>
1050     *
1051     * ecm:mixinTypes NOT IN ('Foo', 'Bar')
1052     * <p>
1053     *
1054     * <pre>
1055     * { "$and" : [ { "ecm:primaryType" : { "$in" : [ ... types without Foo nor Bar ...]}} ,
1056     *              { "ecm:mixinTypes" : { "$nin" : [ "Foo" , "Bar]}}]}
1057     * </pre>
1058     */
1059    public DBObject walkMixinTypes(List<String> mixins, boolean include) {
1060        /*
1061         * Primary types that match.
1062         */
1063        Set<String> matchPrimaryTypes;
1064        if (include) {
1065            matchPrimaryTypes = new HashSet<String>();
1066            for (String mixin : mixins) {
1067                matchPrimaryTypes.addAll(getMixinDocumentTypes(mixin));
1068            }
1069        } else {
1070            matchPrimaryTypes = new HashSet<String>(getDocumentTypes());
1071            for (String mixin : mixins) {
1072                matchPrimaryTypes.removeAll(getMixinDocumentTypes(mixin));
1073            }
1074        }
1075        /*
1076         * Instance mixins that match.
1077         */
1078        Set<String> matchMixinTypes = new HashSet<String>();
1079        for (String mixin : mixins) {
1080            if (!isNeverPerInstanceMixin(mixin)) {
1081                matchMixinTypes.add(mixin);
1082            }
1083        }
1084        /*
1085         * MongoDB query generation.
1086         */
1087        // match on primary type
1088        DBObject p = new BasicDBObject(DBSDocument.KEY_PRIMARY_TYPE,
1089                new BasicDBObject(QueryOperators.IN, matchPrimaryTypes));
1090        // match on mixin types
1091        // $in/$nin with an array matches if any/no element of the array matches
1092        String innin = include ? QueryOperators.IN : QueryOperators.NIN;
1093        DBObject m = new BasicDBObject(DBSDocument.KEY_MIXIN_TYPES, new BasicDBObject(innin, matchMixinTypes));
1094        // and/or between those
1095        String op = include ? QueryOperators.OR : QueryOperators.AND;
1096        return new BasicDBObject(op, Arrays.asList(p, m));
1097    }
1098
1099}