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