001/*
002 * CDDL HEADER START
003 *
004 * The contents of this file are subject to the terms of the
005 * Common Development and Distribution License, Version 1.0 only
006 * (the "License").  You may not use this file except in compliance
007 * with the License.
008 *
009 * You can obtain a copy of the license at legal-notices/CDDLv1_0.txt
010 * or http://forgerock.org/license/CDDLv1.0.html.
011 * See the License for the specific language governing permissions
012 * and limitations under the License.
013 *
014 * When distributing Covered Code, include this CDDL HEADER in each
015 * file and include the License file at legal-notices/CDDLv1_0.txt.
016 * If applicable, add the following below this CDDL HEADER, with the
017 * fields enclosed by brackets "[]" replaced with your own identifying
018 * information:
019 *      Portions Copyright [yyyy] [name of copyright owner]
020 *
021 * CDDL HEADER END
022 *
023 *
024 *      Copyright 2009 Sun Microsystems, Inc.
025 *      Portions copyright 2012-2015 ForgeRock AS.
026 */
027package org.forgerock.opendj.ldap;
028
029import java.util.ArrayList;
030import java.util.List;
031
032import org.forgerock.i18n.LocalizableMessage;
033import org.forgerock.i18n.LocalizedIllegalArgumentException;
034import org.forgerock.i18n.slf4j.LocalizedLogger;
035import org.forgerock.opendj.ldap.schema.MatchingRule;
036import org.forgerock.opendj.ldap.schema.MatchingRuleUse;
037import org.forgerock.opendj.ldap.schema.Schema;
038import org.forgerock.opendj.ldap.schema.UnknownSchemaElementException;
039
040import com.forgerock.opendj.util.StaticUtils;
041
042/**
043 * An interface for determining whether entries match a {@code Filter}.
044 */
045public final class Matcher {
046    private static final class AndMatcherImpl extends MatcherImpl {
047        private final List<MatcherImpl> subMatchers;
048
049        private AndMatcherImpl(final List<MatcherImpl> subMatchers) {
050            this.subMatchers = subMatchers;
051        }
052
053        @Override
054        public ConditionResult matches(final Entry entry) {
055            ConditionResult r = ConditionResult.TRUE;
056            for (final MatcherImpl m : subMatchers) {
057                final ConditionResult p = m.matches(entry);
058                if (p == ConditionResult.FALSE) {
059                    return p;
060                }
061                r = ConditionResult.and(r, p);
062            }
063            return r;
064        }
065    }
066
067    private static final class AssertionMatcherImpl extends MatcherImpl {
068        private final Assertion assertion;
069
070        private final AttributeDescription attributeDescription;
071
072        private final boolean dnAttributes;
073
074        private final MatchingRule rule;
075
076        private final MatchingRuleUse ruleUse;
077
078        private AssertionMatcherImpl(final AttributeDescription attributeDescription,
079                final MatchingRule rule, final MatchingRuleUse ruleUse, final Assertion assertion,
080                final boolean dnAttributes) {
081            this.attributeDescription = attributeDescription;
082            this.rule = rule;
083            this.ruleUse = ruleUse;
084            this.assertion = assertion;
085            this.dnAttributes = dnAttributes;
086        }
087
088        @Override
089        public ConditionResult matches(final Entry entry) {
090            ConditionResult r = ConditionResult.FALSE;
091            if (attributeDescription != null) {
092                // If the matchingRule field is absent, the type field will be
093                // present and the default equality matching rule is used,
094                // and an equality match is performed for that type.
095
096                // If the type field is present and the matchingRule is present,
097                // the matchValue is compared against the specified attribute
098                // type and its subtypes.
099                final ConditionResult p =
100                        Matcher.matches(entry.getAttribute(attributeDescription), rule, assertion);
101                if (p == ConditionResult.TRUE) {
102                    return p;
103                }
104                r = ConditionResult.or(r, p);
105            } else {
106                // If the type field is absent and the matchingRule is present,
107                // the matchValue is compared against all attributes in an entry
108                // that support that matchingRule.
109                for (final Attribute a : entry.getAllAttributes()) {
110                    if (ruleUse.hasAttribute(a.getAttributeDescription().getAttributeType())) {
111                        final ConditionResult p = Matcher.matches(a, rule, assertion);
112                        if (p == ConditionResult.TRUE) {
113                            return p;
114                        }
115                        r = ConditionResult.or(r, p);
116                    }
117                }
118            }
119
120            if (dnAttributes) {
121                // If the dnAttributes field is set to TRUE, the match is
122                // additionally applied against all the AttributeValueAssertions
123                // in an entry's distinguished name, and it evaluates to TRUE if
124                // there is at least one attribute or subtype in the
125                // distinguished name for which the filter item evaluates to
126                // TRUE.
127                final DN dn = entry.getName();
128                for (final RDN rdn : dn) {
129                    for (final AVA ava : rdn) {
130                        if (ruleUse.hasAttribute(ava.getAttributeType())) {
131                            final ConditionResult p =
132                                    Matcher.matches(ava.getAttributeValue(), rule, assertion);
133                            if (p == ConditionResult.TRUE) {
134                                return p;
135                            }
136                            r = ConditionResult.or(r, p);
137                        }
138                    }
139                }
140            }
141            return r;
142        }
143    }
144
145    private static class FalseMatcherImpl extends MatcherImpl {
146        @Override
147        public ConditionResult matches(final Entry entry) {
148            return ConditionResult.FALSE;
149        }
150    }
151
152    private static abstract class MatcherImpl {
153        public abstract ConditionResult matches(Entry entry);
154    }
155
156    private static final class NotMatcherImpl extends MatcherImpl {
157        private final MatcherImpl subFilter;
158
159        private NotMatcherImpl(final MatcherImpl subFilter) {
160            this.subFilter = subFilter;
161        }
162
163        @Override
164        public ConditionResult matches(final Entry entry) {
165            return ConditionResult.not(subFilter.matches(entry));
166        }
167    }
168
169    private static final class OrMatcherImpl extends MatcherImpl {
170        private final List<MatcherImpl> subMatchers;
171
172        private OrMatcherImpl(final List<MatcherImpl> subMatchers) {
173            this.subMatchers = subMatchers;
174        }
175
176        @Override
177        public ConditionResult matches(final Entry entry) {
178            ConditionResult r = ConditionResult.FALSE;
179            for (final MatcherImpl m : subMatchers) {
180                final ConditionResult p = m.matches(entry);
181                if (p == ConditionResult.TRUE) {
182                    return p;
183                }
184                r = ConditionResult.or(r, p);
185            }
186            return r;
187        }
188    }
189
190    private static final class PresentMatcherImpl extends MatcherImpl {
191        private final AttributeDescription attribute;
192
193        private PresentMatcherImpl(final AttributeDescription attribute) {
194            this.attribute = attribute;
195        }
196
197        @Override
198        public ConditionResult matches(final Entry entry) {
199            return entry.getAttribute(attribute) == null ? ConditionResult.FALSE
200                    : ConditionResult.TRUE;
201        }
202    }
203
204    private static class TrueMatcherImpl extends MatcherImpl {
205        @Override
206        public ConditionResult matches(final Entry entry) {
207            return ConditionResult.TRUE;
208        }
209    }
210
211    private static class UndefinedMatcherImpl extends MatcherImpl {
212        @Override
213        public ConditionResult matches(final Entry entry) {
214            return ConditionResult.UNDEFINED;
215        }
216    }
217
218    /**
219     * A visitor which is used to transform a filter into a matcher.
220     */
221    private static final class Visitor implements FilterVisitor<MatcherImpl, Schema> {
222        public MatcherImpl visitAndFilter(final Schema schema, final List<Filter> subFilters) {
223            if (subFilters.isEmpty()) {
224                logger.trace(LocalizableMessage.raw("Empty add filter component. Will always return TRUE"));
225                return TRUE;
226            }
227
228            final List<MatcherImpl> subMatchers = new ArrayList<>(subFilters.size());
229            for (final Filter f : subFilters) {
230                subMatchers.add(f.accept(this, schema));
231            }
232            return new AndMatcherImpl(subMatchers);
233        }
234
235        public MatcherImpl visitApproxMatchFilter(final Schema schema,
236                final String attributeDescription, final ByteString assertionValue) {
237            final AttributeDescription ad;
238            try {
239                ad = AttributeDescription.valueOf(attributeDescription, schema);
240            } catch (final LocalizedIllegalArgumentException e) {
241                // TODO: I18N
242                logger.warn(LocalizableMessage.raw(
243                        "Attribute description %s is not recognized", attributeDescription, e));
244                return UNDEFINED;
245            }
246
247            final MatchingRule rule = ad.getAttributeType().getApproximateMatchingRule();
248            if (rule == null) {
249                // TODO: I18N
250                logger.warn(LocalizableMessage.raw("The attribute type %s does not define an approximate matching rule",
251                        attributeDescription));
252                return UNDEFINED;
253            }
254
255            final Assertion assertion;
256            try {
257                assertion = rule.getAssertion(assertionValue);
258            } catch (final DecodeException de) {
259                // TODO: I18N
260                logger.warn(LocalizableMessage.raw("The assertion value %s is invalid", assertionValue, de));
261                return UNDEFINED;
262            }
263            return new AssertionMatcherImpl(ad, rule, null, assertion, false);
264        }
265
266        public MatcherImpl visitEqualityMatchFilter(final Schema schema,
267                final String attributeDescription, final ByteString assertionValue) {
268            final AttributeDescription ad;
269            try {
270                ad = AttributeDescription.valueOf(attributeDescription, schema);
271            } catch (final LocalizedIllegalArgumentException e) {
272                // TODO: I18N
273                logger.warn(LocalizableMessage.raw("Attribute description %s is not recognized",
274                        attributeDescription, e));
275                return UNDEFINED;
276            }
277
278            final MatchingRule rule = ad.getAttributeType().getEqualityMatchingRule();
279            if (rule == null) {
280                // TODO: I18N
281                logger.warn(LocalizableMessage.raw("The attribute type %s does not define an equality matching rule",
282                        attributeDescription));
283                return UNDEFINED;
284            }
285
286            final Assertion assertion;
287            try {
288                assertion = rule.getAssertion(assertionValue);
289            } catch (final DecodeException de) {
290                // TODO: I18N
291                logger.warn(LocalizableMessage.raw("The assertion value %s is invalid", assertionValue, de));
292                return UNDEFINED;
293            }
294            return new AssertionMatcherImpl(ad, rule, null, assertion, false);
295        }
296
297        public MatcherImpl visitExtensibleMatchFilter(final Schema schema,
298                final String matchingRule, final String attributeDescription,
299                final ByteString assertionValue, final boolean dnAttributes) {
300            AttributeDescription ad = null;
301            MatchingRule rule = null;
302            MatchingRuleUse ruleUse = null;
303            Assertion assertion;
304
305            if (matchingRule != null) {
306                try {
307                    rule = schema.getMatchingRule(matchingRule);
308                } catch (final UnknownSchemaElementException e) {
309                    // TODO: I18N
310                    logger.warn(LocalizableMessage.raw("Matching rule %s is not recognized", matchingRule));
311                    return UNDEFINED;
312                }
313            }
314
315            if (attributeDescription != null) {
316                try {
317                    ad = AttributeDescription.valueOf(attributeDescription, schema);
318                } catch (final LocalizedIllegalArgumentException e) {
319                    // TODO: I18N
320                    logger.warn(LocalizableMessage.raw("Attribute description %s is not recognized",
321                            attributeDescription, e));
322                    return UNDEFINED;
323                }
324
325                if (rule == null) {
326                    rule = ad.getAttributeType().getEqualityMatchingRule();
327                    if (rule == null) {
328                        // TODO: I18N
329                        logger.warn(LocalizableMessage.raw(
330                                "The attribute type %s does not define an equality matching rule",
331                                attributeDescription));
332                        return UNDEFINED;
333                    }
334                } else {
335                    try {
336                        ruleUse = schema.getMatchingRuleUse(rule);
337                        if (!ruleUse.hasAttribute(ad.getAttributeType())) {
338                            // TODO: I18N
339                            logger.warn(LocalizableMessage.raw(
340                                    "The matching rule %s is not valid for attribute type %s",
341                                    matchingRule, attributeDescription));
342                            return UNDEFINED;
343                        }
344                    } catch (final UnknownSchemaElementException e) {
345                        // TODO: I18N
346                        logger.warn(LocalizableMessage.raw("No matching rule use is defined for matching rule %s",
347                                matchingRule));
348                        return UNDEFINED;
349                    }
350                }
351            } else {
352                try {
353                    ruleUse = schema.getMatchingRuleUse(rule);
354                } catch (final UnknownSchemaElementException e) {
355                    // TODO: I18N
356                    logger.warn(LocalizableMessage.raw("No matching rule use is defined for matching rule %s",
357                            matchingRule));
358                    return UNDEFINED;
359                }
360            }
361
362            try {
363                assertion = rule.getAssertion(assertionValue);
364            } catch (final DecodeException de) {
365                // TODO: I18N
366                logger.warn(LocalizableMessage.raw("The assertion value %s is invalid", assertionValue, de));
367                return UNDEFINED;
368            }
369            return new AssertionMatcherImpl(ad, rule, ruleUse, assertion, dnAttributes);
370        }
371
372        public MatcherImpl visitGreaterOrEqualFilter(final Schema schema,
373                final String attributeDescription, final ByteString assertionValue) {
374            final AttributeDescription ad;
375            try {
376                ad = AttributeDescription.valueOf(attributeDescription, schema);
377            } catch (final LocalizedIllegalArgumentException e) {
378                // TODO: I18N
379                logger.warn(LocalizableMessage.raw("Attribute description %s is not recognized",
380                        attributeDescription, e));
381
382                return UNDEFINED;
383            }
384
385            final MatchingRule rule = ad.getAttributeType().getOrderingMatchingRule();
386            if (rule == null) {
387                // TODO: I18N
388                logger.warn(LocalizableMessage.raw("The attribute type %s does not define an ordering matching rule",
389                        attributeDescription));
390                return UNDEFINED;
391            }
392
393            final Assertion assertion;
394            try {
395                assertion = rule.getGreaterOrEqualAssertion(assertionValue);
396            } catch (final DecodeException de) {
397                // TODO: I18N
398                logger.warn(LocalizableMessage.raw("The assertion value %s is invalid", assertionValue, de));
399                return UNDEFINED;
400            }
401            return new AssertionMatcherImpl(ad, rule, null, assertion, false);
402        }
403
404        public MatcherImpl visitLessOrEqualFilter(final Schema schema,
405                final String attributeDescription, final ByteString assertionValue) {
406            final AttributeDescription ad;
407            try {
408                ad = AttributeDescription.valueOf(attributeDescription, schema);
409            } catch (final LocalizedIllegalArgumentException e) {
410                // TODO: I18N
411                logger.warn(LocalizableMessage.raw("Attribute description %s is not recognized",
412                        attributeDescription, e));
413                return UNDEFINED;
414            }
415
416            final MatchingRule rule = ad.getAttributeType().getOrderingMatchingRule();
417            if (rule == null) {
418                // TODO: I18N
419                logger.warn(LocalizableMessage.raw("The attribute type %s does not define an ordering matching rule",
420                        attributeDescription));
421                return UNDEFINED;
422            }
423
424            final Assertion assertion;
425            try {
426                assertion = rule.getLessOrEqualAssertion(assertionValue);
427            } catch (final DecodeException de) {
428                // TODO: I18N
429                logger.warn(LocalizableMessage.raw("The assertion value %s is invalid", assertionValue , de));
430                return UNDEFINED;
431            }
432            return new AssertionMatcherImpl(ad, rule, null, assertion, false);
433        }
434
435        public MatcherImpl visitNotFilter(final Schema schema, final Filter subFilter) {
436            final MatcherImpl subMatcher = subFilter.accept(this, schema);
437            return new NotMatcherImpl(subMatcher);
438        }
439
440        public MatcherImpl visitOrFilter(final Schema schema, final List<Filter> subFilters) {
441            if (subFilters.isEmpty()) {
442                logger.trace(LocalizableMessage.raw("Empty or filter component. Will always return FALSE"));
443                return FALSE;
444            }
445
446            final List<MatcherImpl> subMatchers = new ArrayList<>(subFilters.size());
447            for (final Filter f : subFilters) {
448                subMatchers.add(f.accept(this, schema));
449            }
450            return new OrMatcherImpl(subMatchers);
451        }
452
453        public MatcherImpl visitPresentFilter(final Schema schema, final String attributeDescription) {
454            AttributeDescription ad;
455            try {
456                ad = AttributeDescription.valueOf(attributeDescription, schema);
457            } catch (final LocalizedIllegalArgumentException e) {
458                // TODO: I18N
459                logger.warn(LocalizableMessage.raw("Attribute description %s is not recognized",
460                        attributeDescription, e));
461                return UNDEFINED;
462            }
463
464            return new PresentMatcherImpl(ad);
465        }
466
467        public MatcherImpl visitSubstringsFilter(final Schema schema,
468                final String attributeDescription, final ByteString initialSubstring,
469                final List<ByteString> anySubstrings, final ByteString finalSubstring) {
470            final AttributeDescription ad;
471            try {
472                ad = AttributeDescription.valueOf(attributeDescription, schema);
473            } catch (final LocalizedIllegalArgumentException e) {
474                // TODO: I18N
475                logger.warn(LocalizableMessage.raw("Attribute description %s is not recognized",
476                        attributeDescription, e));
477                return UNDEFINED;
478            }
479
480            final MatchingRule rule = ad.getAttributeType().getSubstringMatchingRule();
481            if (rule == null) {
482                // TODO: I18N
483                logger.warn(LocalizableMessage.raw("The attribute type %s does not define an substring matching rule",
484                        attributeDescription));
485                return UNDEFINED;
486            }
487
488            final Assertion assertion;
489            try {
490                assertion = rule.getSubstringAssertion(initialSubstring, anySubstrings, finalSubstring);
491            } catch (final DecodeException de) {
492                // TODO: I18N
493                logger.warn(LocalizableMessage.raw("The substring assertion values contain an invalid value", de));
494                return UNDEFINED;
495            }
496            return new AssertionMatcherImpl(ad, rule, null, assertion, false);
497        }
498
499        public MatcherImpl visitUnrecognizedFilter(final Schema schema, final byte filterTag,
500                final ByteString filterBytes) {
501            // TODO: I18N
502            logger.warn(LocalizableMessage.raw("The type of filtering requested with tag %s is not implemented",
503                    StaticUtils.byteToHex(filterTag)));
504            return UNDEFINED;
505        }
506    }
507
508    private static final LocalizedLogger logger = LocalizedLogger.getLoggerForThisClass();
509
510    private static final MatcherImpl FALSE = new FalseMatcherImpl();
511    private static final MatcherImpl TRUE = new TrueMatcherImpl();
512    private static final MatcherImpl UNDEFINED = new UndefinedMatcherImpl();
513
514    private static final FilterVisitor<MatcherImpl, Schema> VISITOR = new Visitor();
515
516    private static ConditionResult matches(final Attribute a, final MatchingRule rule,
517            final Assertion assertion) {
518        ConditionResult r = ConditionResult.FALSE;
519        if (a != null) {
520            for (final ByteString v : a) {
521                switch (matches(v, rule, assertion)) {
522                case TRUE:
523                    return ConditionResult.TRUE;
524                case FALSE:
525                    continue;
526                case UNDEFINED:
527                    r = ConditionResult.UNDEFINED;
528                }
529            }
530        }
531        return r;
532    }
533
534    private static ConditionResult matches(final ByteString v, final MatchingRule rule,
535            final Assertion assertion) {
536        try {
537            final ByteString normalizedValue = rule.normalizeAttributeValue(v);
538            return assertion.matches(normalizedValue);
539        } catch (final DecodeException de) {
540            // TODO: I18N
541            logger.warn(LocalizableMessage.raw(
542                    "The attribute value %s is invalid for matching rule %s. Possible schema error?",
543                    v, rule.getNameOrOID(), de));
544            return ConditionResult.UNDEFINED;
545        }
546    }
547
548    private final MatcherImpl impl;
549
550    Matcher(final Filter filter, final Schema schema) {
551        this.impl = filter.accept(VISITOR, schema);
552    }
553
554    /**
555     * Indicates whether this filter {@code Matcher} matches the provided
556     * {@code Entry}.
557     *
558     * @param entry
559     *            The entry to be matched.
560     * @return The result of matching the provided {@code Entry} against this
561     *         filter {@code Matcher}.
562     */
563    public ConditionResult matches(final Entry entry) {
564        return impl.matches(entry);
565    }
566}