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-2011 Sun Microsystems, Inc.
015 * Portions copyright 2012-2016 ForgeRock AS.
016 */
017package org.forgerock.opendj.ldap;
018
019import static com.forgerock.opendj.ldap.CoreMessages.*;
020import static com.forgerock.opendj.util.StaticUtils.*;
021
022import java.util.ArrayList;
023import java.util.Collection;
024import java.util.Collections;
025import java.util.LinkedList;
026import java.util.List;
027
028import org.forgerock.i18n.LocalizableMessage;
029import org.forgerock.i18n.LocalizedIllegalArgumentException;
030import org.forgerock.opendj.ldap.schema.Schema;
031import org.forgerock.util.Reject;
032
033/**
034 * A search filter as defined in RFC 4511. In addition this class also provides
035 * support for the absolute true and absolute false filters as defined in RFC
036 * 4526.
037 * <p>
038 * This class provides many factory methods for creating common types of filter.
039 * Applications interact with a filter using {@link FilterVisitor} which is
040 * applied to a filter using the {@link #accept(FilterVisitor, Object)} method.
041 * <p>
042 * The RFC 4515 string representation of a filter can be generated using the
043 * {@link #toString} methods and parsed using the {@link #valueOf(String)}
044 * factory method.
045 * <p>
046 * Filters can be constructed using the various factory methods. For example,
047 * the following code illustrates how to create a filter having the string
048 * representation "{@code (&(cn=bjensen)(age>=21))}":
049 *
050 * <pre>
051 * import static org.forgerock.opendj.Filter.*;
052 *
053 * Filter filter = and(equality("cn", "bjensen"), greaterOrEqual("age", 21));
054 *
055 * // Alternatively use a filter template:
056 * Filter filter = Filter.format("(&(cn=%s)(age>=%s))", "bjensen", 21);
057 * </pre>
058 *
059 * @see <a href="http://tools.ietf.org/html/rfc4511">RFC 4511 - Lightweight
060 *      Directory Access Protocol (LDAP): The Protocol </a>
061 * @see <a href="http://tools.ietf.org/html/rfc4515">RFC 4515 - String
062 *      Representation of Search Filters </a>
063 * @see <a href="http://tools.ietf.org/html/rfc4526">RFC 4526 - Absolute True
064 *      and False Filters </a>
065 */
066public final class Filter {
067
068    /** The asterisk character. */
069    private static final byte ASTERISK = 0x2A;
070
071    /** The backslash character. */
072    private static final byte BACKSLASH = 0x5C;
073
074    private static final class AndImpl extends Impl {
075        private final List<Filter> subFilters;
076
077        public AndImpl(final List<Filter> subFilters) {
078            this.subFilters = subFilters;
079        }
080
081        @Override
082        public <R, P> R accept(final FilterVisitor<R, P> v, final P p) {
083            return v.visitAndFilter(p, subFilters);
084        }
085
086    }
087
088    private static final class ApproxMatchImpl extends Impl {
089
090        private final ByteString assertionValue;
091
092        private final String attributeDescription;
093
094        public ApproxMatchImpl(final String attributeDescription, final ByteString assertionValue) {
095            this.attributeDescription = attributeDescription;
096            this.assertionValue = assertionValue;
097        }
098
099        @Override
100        public <R, P> R accept(final FilterVisitor<R, P> v, final P p) {
101            return v.visitApproxMatchFilter(p, attributeDescription, assertionValue);
102        }
103
104    }
105
106    private static final class EqualityMatchImpl extends Impl {
107
108        private final ByteString assertionValue;
109
110        private final String attributeDescription;
111
112        public EqualityMatchImpl(final String attributeDescription, final ByteString assertionValue) {
113            this.attributeDescription = attributeDescription;
114            this.assertionValue = assertionValue;
115        }
116
117        @Override
118        public <R, P> R accept(final FilterVisitor<R, P> v, final P p) {
119            return v.visitEqualityMatchFilter(p, attributeDescription, assertionValue);
120        }
121
122    }
123
124    private static final class ExtensibleMatchImpl extends Impl {
125        private final String attributeDescription;
126
127        private final boolean dnAttributes;
128
129        private final String matchingRule;
130
131        private final ByteString matchValue;
132
133        public ExtensibleMatchImpl(final String matchingRule, final String attributeDescription,
134                final ByteString matchValue, final boolean dnAttributes) {
135            this.matchingRule = matchingRule;
136            this.attributeDescription = attributeDescription;
137            this.matchValue = matchValue;
138            this.dnAttributes = dnAttributes;
139        }
140
141        @Override
142        public <R, P> R accept(final FilterVisitor<R, P> v, final P p) {
143            return v.visitExtensibleMatchFilter(p, matchingRule, attributeDescription, matchValue,
144                    dnAttributes);
145        }
146
147    }
148
149    private static final class GreaterOrEqualImpl extends Impl {
150
151        private final ByteString assertionValue;
152
153        private final String attributeDescription;
154
155        public GreaterOrEqualImpl(final String attributeDescription, final ByteString assertionValue) {
156            this.attributeDescription = attributeDescription;
157            this.assertionValue = assertionValue;
158        }
159
160        @Override
161        public <R, P> R accept(final FilterVisitor<R, P> v, final P p) {
162            return v.visitGreaterOrEqualFilter(p, attributeDescription, assertionValue);
163        }
164
165    }
166
167    private static abstract class Impl {
168        protected Impl() {
169            // Nothing to do.
170        }
171
172        public abstract <R, P> R accept(FilterVisitor<R, P> v, P p);
173    }
174
175    private static final class LessOrEqualImpl extends Impl {
176
177        private final ByteString assertionValue;
178
179        private final String attributeDescription;
180
181        public LessOrEqualImpl(final String attributeDescription, final ByteString assertionValue) {
182            this.attributeDescription = attributeDescription;
183            this.assertionValue = assertionValue;
184        }
185
186        @Override
187        public <R, P> R accept(final FilterVisitor<R, P> v, final P p) {
188            return v.visitLessOrEqualFilter(p, attributeDescription, assertionValue);
189        }
190
191    }
192
193    private static final class NotImpl extends Impl {
194        private final Filter subFilter;
195
196        public NotImpl(final Filter subFilter) {
197            this.subFilter = subFilter;
198        }
199
200        @Override
201        public <R, P> R accept(final FilterVisitor<R, P> v, final P p) {
202            return v.visitNotFilter(p, subFilter);
203        }
204
205    }
206
207    private static final class OrImpl extends Impl {
208        private final List<Filter> subFilters;
209
210        public OrImpl(final List<Filter> subFilters) {
211            this.subFilters = subFilters;
212        }
213
214        @Override
215        public <R, P> R accept(final FilterVisitor<R, P> v, final P p) {
216            return v.visitOrFilter(p, subFilters);
217        }
218
219    }
220
221    private static final class PresentImpl extends Impl {
222
223        private final String attributeDescription;
224
225        public PresentImpl(final String attributeDescription) {
226            this.attributeDescription = attributeDescription;
227        }
228
229        @Override
230        public <R, P> R accept(final FilterVisitor<R, P> v, final P p) {
231            return v.visitPresentFilter(p, attributeDescription);
232        }
233
234    }
235
236    private static final class SubstringsImpl extends Impl {
237
238        private final List<ByteString> anyStrings;
239
240        private final String attributeDescription;
241
242        private final ByteString finalString;
243
244        private final ByteString initialString;
245
246        public SubstringsImpl(final String attributeDescription, final ByteString initialString,
247                final List<ByteString> anyStrings, final ByteString finalString) {
248            this.attributeDescription = attributeDescription;
249            this.initialString = initialString;
250            this.anyStrings = anyStrings;
251            this.finalString = finalString;
252
253        }
254
255        @Override
256        public <R, P> R accept(final FilterVisitor<R, P> v, final P p) {
257            return v.visitSubstringsFilter(p, attributeDescription, initialString, anyStrings,
258                    finalString);
259        }
260
261    }
262
263    private static final class UnrecognizedImpl extends Impl {
264
265        private final ByteString filterBytes;
266
267        private final byte filterTag;
268
269        public UnrecognizedImpl(final byte filterTag, final ByteString filterBytes) {
270            this.filterTag = filterTag;
271            this.filterBytes = filterBytes;
272        }
273
274        @Override
275        public <R, P> R accept(final FilterVisitor<R, P> v, final P p) {
276            return v.visitUnrecognizedFilter(p, filterTag, filterBytes);
277        }
278
279    }
280
281    /** RFC 4526 - FALSE filter. */
282    private static final Filter FALSE = new Filter(new OrImpl(Collections.<Filter> emptyList()));
283
284    /** Heavily used (objectClass=*) filter. */
285    private static final Filter OBJECT_CLASS_PRESENT = new Filter(new PresentImpl("objectClass"));
286
287    private static final FilterVisitor<StringBuilder, StringBuilder> TO_STRING_VISITOR =
288            new FilterVisitor<StringBuilder, StringBuilder>() {
289
290                @Override
291                public StringBuilder visitAndFilter(final StringBuilder builder,
292                        final List<Filter> subFilters) {
293                    builder.append("(&");
294                    for (final Filter subFilter : subFilters) {
295                        subFilter.accept(this, builder);
296                    }
297                    builder.append(')');
298                    return builder;
299                }
300
301                @Override
302                public StringBuilder visitOrFilter(final StringBuilder builder,
303                        final List<Filter> subFilters) {
304                    builder.append("(|");
305                    for (final Filter subFilter : subFilters) {
306                        subFilter.accept(this, builder);
307                    }
308                    builder.append(')');
309                    return builder;
310                }
311
312                @Override
313                public StringBuilder visitApproxMatchFilter(final StringBuilder builder,
314                        final String attributeDescription, final ByteString assertionValue) {
315                    return visitBinaryOperator(builder, attributeDescription, "~=", assertionValue);
316                }
317
318                @Override
319                public StringBuilder visitEqualityMatchFilter(final StringBuilder builder,
320                        final String attributeDescription, final ByteString assertionValue) {
321                    return visitBinaryOperator(builder, attributeDescription, "=", assertionValue);
322                }
323
324                @Override
325                public StringBuilder visitGreaterOrEqualFilter(final StringBuilder builder,
326                        final String attributeDescription, final ByteString assertionValue) {
327                    return visitBinaryOperator(builder, attributeDescription, ">=", assertionValue);
328                }
329
330                @Override
331                public StringBuilder visitLessOrEqualFilter(final StringBuilder builder,
332                        final String attributeDescription, final ByteString assertionValue) {
333                    return visitBinaryOperator(builder, attributeDescription, "<=", assertionValue);
334                }
335
336                private StringBuilder visitBinaryOperator(final StringBuilder builder,
337                        final String attributeDescription, final String operator, final ByteString assertionValue) {
338                    builder.append('(');
339                    builder.append(attributeDescription);
340                    builder.append(operator);
341                    valueToFilterString(builder, assertionValue);
342                    builder.append(')');
343                    return builder;
344                }
345
346                @Override
347                public StringBuilder visitExtensibleMatchFilter(final StringBuilder builder,
348                        final String matchingRule, final String attributeDescription,
349                        final ByteString assertionValue, final boolean dnAttributes) {
350                    builder.append('(');
351
352                    if (attributeDescription != null) {
353                        builder.append(attributeDescription);
354                    }
355
356                    if (dnAttributes) {
357                        builder.append(":dn");
358                    }
359
360                    if (matchingRule != null) {
361                        builder.append(':');
362                        builder.append(matchingRule);
363                    }
364
365                    builder.append(":=");
366                    valueToFilterString(builder, assertionValue);
367                    builder.append(')');
368                    return builder;
369                }
370
371                @Override
372                public StringBuilder visitNotFilter(final StringBuilder builder,
373                        final Filter subFilter) {
374                    builder.append("(!");
375                    subFilter.accept(this, builder);
376                    builder.append(')');
377                    return builder;
378                }
379
380                @Override
381                public StringBuilder visitPresentFilter(final StringBuilder builder,
382                        final String attributeDescription) {
383                    builder.append('(');
384                    builder.append(attributeDescription);
385                    builder.append("=*)");
386                    return builder;
387                }
388
389                @Override
390                public StringBuilder visitSubstringsFilter(final StringBuilder builder,
391                        final String attributeDescription, final ByteString initialSubstring,
392                        final List<ByteString> anySubstrings, final ByteString finalSubstring) {
393                    builder.append('(');
394                    builder.append(attributeDescription);
395                    builder.append("=");
396                    if (initialSubstring != null) {
397                        valueToFilterString(builder, initialSubstring);
398                    }
399                    for (final ByteString anySubstring : anySubstrings) {
400                        builder.append('*');
401                        valueToFilterString(builder, anySubstring);
402                    }
403                    builder.append('*');
404                    if (finalSubstring != null) {
405                        valueToFilterString(builder, finalSubstring);
406                    }
407                    builder.append(')');
408                    return builder;
409                }
410
411                @Override
412                public StringBuilder visitUnrecognizedFilter(final StringBuilder builder,
413                        final byte filterTag, final ByteString filterBytes) {
414                    // Fake up a representation.
415                    builder.append('(');
416                    builder.append(byteToHex(filterTag));
417                    builder.append(':');
418                    builder.append(filterBytes.toHexString());
419                    builder.append(')');
420                    return builder;
421                }
422            };
423
424    /** RFC 4526 - TRUE filter. */
425    private static final Filter TRUE = new Filter(new AndImpl(Collections.<Filter> emptyList()));
426
427    /**
428     * Returns the {@code absolute false} filter as defined in RFC 4526 which is
429     * comprised of an {@code or} filter containing zero components.
430     *
431     * @return The absolute false filter.
432     * @see <a href="http://tools.ietf.org/html/rfc4526">RFC 4526</a>
433     */
434    public static Filter alwaysFalse() {
435        return FALSE;
436    }
437
438    /**
439     * Returns the {@code absolute true} filter as defined in RFC 4526 which is
440     * comprised of an {@code and} filter containing zero components.
441     *
442     * @return The absolute true filter.
443     * @see <a href="http://tools.ietf.org/html/rfc4526">RFC 4526</a>
444     */
445    public static Filter alwaysTrue() {
446        return TRUE;
447    }
448
449    /**
450     * Creates a new {@code and} filter using the provided list of sub-filters.
451     * <p>
452     * Creating a new {@code and} filter with a {@code null} or empty list of
453     * sub-filters is equivalent to calling {@link #alwaysTrue()}.
454     *
455     * @param subFilters
456     *            The list of sub-filters, may be empty or {@code null}.
457     * @return The newly created {@code and} filter.
458     */
459    public static Filter and(final Collection<Filter> subFilters) {
460        if (subFilters == null || subFilters.isEmpty()) {
461            // RFC 4526 - TRUE filter.
462            return alwaysTrue();
463        } else if (subFilters.size() == 1) {
464            final Filter subFilter = subFilters.iterator().next();
465            Reject.ifNull(subFilter);
466            return new Filter(new AndImpl(Collections.singletonList(subFilter)));
467        } else {
468            final List<Filter> subFiltersList = new ArrayList<>(subFilters.size());
469            for (final Filter subFilter : subFilters) {
470                Reject.ifNull(subFilter);
471                subFiltersList.add(subFilter);
472            }
473            return new Filter(new AndImpl(Collections.unmodifiableList(subFiltersList)));
474        }
475    }
476
477    /**
478     * Creates a new {@code and} filter using the provided list of sub-filters.
479     * <p>
480     * Creating a new {@code and} filter with a {@code null} or empty list of
481     * sub-filters is equivalent to calling {@link #alwaysTrue()}.
482     *
483     * @param subFilters
484     *            The list of sub-filters, may be empty or {@code null}.
485     * @return The newly created {@code and} filter.
486     */
487    public static Filter and(final Filter... subFilters) {
488        if (subFilters == null || subFilters.length == 0) {
489            // RFC 4526 - TRUE filter.
490            return alwaysTrue();
491        } else if (subFilters.length == 1) {
492            Reject.ifNull(subFilters[0]);
493            return new Filter(new AndImpl(Collections.singletonList(subFilters[0])));
494        } else {
495            final List<Filter> subFiltersList = new ArrayList<>(subFilters.length);
496            for (final Filter subFilter : subFilters) {
497                Reject.ifNull(subFilter);
498                subFiltersList.add(subFilter);
499            }
500            return new Filter(new AndImpl(Collections.unmodifiableList(subFiltersList)));
501        }
502    }
503
504    /**
505     * Creates a new {@code approximate match} filter using the provided
506     * attribute description and assertion value.
507     * <p>
508     * If {@code assertionValue} is not an instance of {@code ByteString} then
509     * it will be converted using the {@link ByteString#valueOfObject(Object)} method.
510     *
511     * @param attributeDescription
512     *            The attribute description.
513     * @param assertionValue
514     *            The assertion value.
515     * @return The newly created {@code approximate match} filter.
516     */
517    public static Filter approx(final String attributeDescription, final Object assertionValue) {
518        Reject.ifNull(attributeDescription, assertionValue);
519        return new Filter(new ApproxMatchImpl(attributeDescription, ByteString
520                .valueOfObject(assertionValue)));
521    }
522
523    /**
524     * Creates a new {@code equality match} filter using the provided attribute
525     * description and assertion value.
526     * <p>
527     * If {@code assertionValue} is not an instance of {@code ByteString} then
528     * it will be converted using the {@link ByteString#valueOfObject(Object)} method.
529     *
530     * @param attributeDescription
531     *            The attribute description.
532     * @param assertionValue
533     *            The assertion value.
534     * @return The newly created {@code equality match} filter.
535     */
536    public static Filter equality(final String attributeDescription, final Object assertionValue) {
537        Reject.ifNull(attributeDescription, assertionValue);
538        return new Filter(new EqualityMatchImpl(attributeDescription, ByteString
539                .valueOfObject(assertionValue)));
540    }
541
542    /**
543     * Returns the LDAP string representation of the provided filter assertion
544     * value in a form suitable for substitution directly into a filter string.
545     * This method may be useful in cases where a filter is to be constructed
546     * from a filter template using {@code String#format(String, Object...)}.
547     * The following example illustrates two approaches to constructing an
548     * equality filter:
549     *
550     * <pre>
551     * // This may contain user input.
552     * String assertionValue = ...;
553     *
554     * // Using the equality filter constructor:
555     * Filter filter = Filter.equality("cn", assertionValue);
556     *
557     * // Using a String template:
558     * String filterTemplate = "(cn=%s)";
559     * String filterString = String.format(filterTemplate,
560     *                                     Filter.escapeAssertionValue(assertionValue));
561     * Filter filter = Filter.valueOf(filterString);
562     * </pre>
563     *
564     * If {@code assertionValue} is not an instance of {@code ByteString} then
565     * it will be converted using the {@link ByteString#valueOfObject(Object)} method.
566     * <p>
567     * <b>Note:</b> assertion values do not and should not be escaped before
568     * passing them to constructors like {@link #equality(String, Object)}.
569     * Escaping is only required when creating filter strings.
570     *
571     * @param assertionValue
572     *            The assertion value.
573     * @return The LDAP string representation of the provided filter assertion
574     *         value in a form suitable for substitution directly into a filter
575     *         string.
576     * @see #format(String, Object...)
577     */
578    public static String escapeAssertionValue(final Object assertionValue) {
579        Reject.ifNull(assertionValue);
580        final ByteString bytes = ByteString.valueOfObject(assertionValue);
581        final StringBuilder builder = new StringBuilder(bytes.length());
582        valueToFilterString(builder, bytes);
583        return builder.toString();
584    }
585
586    /**
587     * Creates a new {@code extensible match} filter.
588     * <p>
589     * If {@code assertionValue} is not an instance of {@code ByteString} then
590     * it will be converted using the {@link ByteString#valueOfObject(Object)} method.
591     *
592     * @param matchingRule
593     *            The matching rule name, may be {@code null} if
594     *            {@code attributeDescription} is specified.
595     * @param attributeDescription
596     *            The attribute description, may be {@code null} if
597     *            {@code matchingRule} is specified.
598     * @param assertionValue
599     *            The assertion value.
600     * @param dnAttributes
601     *            Indicates whether DN matching should be performed.
602     * @return The newly created {@code extensible match} filter.
603     */
604    public static Filter extensible(final String matchingRule, final String attributeDescription,
605            final Object assertionValue, final boolean dnAttributes) {
606        Reject.ifFalse(matchingRule != null || attributeDescription != null,
607                "matchingRule and/or attributeDescription must not be null");
608        Reject.ifNull(assertionValue);
609        return new Filter(new ExtensibleMatchImpl(matchingRule, attributeDescription, ByteString
610                .valueOfObject(assertionValue), dnAttributes));
611    }
612
613    /**
614     * Creates a new {@code greater or equal} filter using the provided
615     * attribute description and assertion value.
616     * <p>
617     * If {@code assertionValue} is not an instance of {@code ByteString} then
618     * it will be converted using the {@link ByteString#valueOfObject(Object)} method.
619     *
620     * @param attributeDescription
621     *            The attribute description.
622     * @param assertionValue
623     *            The assertion value.
624     * @return The newly created {@code greater or equal} filter.
625     */
626    public static Filter greaterOrEqual(final String attributeDescription,
627            final Object assertionValue) {
628        Reject.ifNull(attributeDescription, assertionValue);
629        return new Filter(new GreaterOrEqualImpl(attributeDescription, ByteString
630                .valueOfObject(assertionValue)));
631    }
632
633    /**
634     * Creates a new {@code greater than} filter using the provided attribute
635     * description and assertion value.
636     * <p>
637     * If {@code assertionValue} is not an instance of {@code ByteString} then
638     * it will be converted using the {@link ByteString#valueOfObject(Object)} method.
639     * <p>
640     * <b>NOTE:</b> since LDAP does not support {@code greater than}
641     * comparisons, this method returns a filter of the form
642     * {@code (&(type>=value)(!(type=value)))}. An alternative is to return a
643     * filter of the form {@code (!(type<=value))} , however the outer
644     * {@code not} filter will often prevent directory servers from optimizing
645     * the search using indexes.
646     *
647     * @param attributeDescription
648     *            The attribute description.
649     * @param assertionValue
650     *            The assertion value.
651     * @return The newly created {@code greater than} filter.
652     */
653    public static Filter greaterThan(final String attributeDescription, final Object assertionValue) {
654        return and(greaterOrEqual(attributeDescription, assertionValue), not(equality(
655                attributeDescription, assertionValue)));
656    }
657
658    /**
659     * Creates a new {@code less or equal} filter using the provided attribute
660     * description and assertion value.
661     * <p>
662     * If {@code assertionValue} is not an instance of {@code ByteString} then
663     * it will be converted using the {@link ByteString#valueOfObject(Object)} method.
664     *
665     * @param attributeDescription
666     *            The attribute description.
667     * @param assertionValue
668     *            The assertion value.
669     * @return The newly created {@code less or equal} filter.
670     */
671    public static Filter lessOrEqual(final String attributeDescription, final Object assertionValue) {
672        Reject.ifNull(attributeDescription, assertionValue);
673        return new Filter(new LessOrEqualImpl(attributeDescription, ByteString
674                .valueOfObject(assertionValue)));
675    }
676
677    /**
678     * Creates a new {@code less than} filter using the provided attribute
679     * description and assertion value.
680     * <p>
681     * If {@code assertionValue} is not an instance of {@code ByteString} then
682     * it will be converted using the {@link ByteString#valueOfObject(Object)} method.
683     * <p>
684     * <b>NOTE:</b> since LDAP does not support {@code less than} comparisons,
685     * this method returns a filter of the form
686     * {@code (&(type<=value)(!(type=value)))}. An alternative is to return a
687     * filter of the form {@code (!(type>=value))} , however the outer
688     * {@code not} filter will often prevent directory servers from optimizing
689     * the search using indexes.
690     *
691     * @param attributeDescription
692     *            The attribute description.
693     * @param assertionValue
694     *            The assertion value.
695     * @return The newly created {@code less than} filter.
696     */
697    public static Filter lessThan(final String attributeDescription, final Object assertionValue) {
698        return and(lessOrEqual(attributeDescription, assertionValue), not(equality(
699                attributeDescription, assertionValue)));
700    }
701
702    /**
703     * Creates a new {@code not} filter using the provided sub-filter.
704     *
705     * @param subFilter
706     *            The sub-filter.
707     * @return The newly created {@code not} filter.
708     */
709    public static Filter not(final Filter subFilter) {
710        Reject.ifNull(subFilter);
711        return new Filter(new NotImpl(subFilter));
712    }
713
714    /**
715     * Returns the {@code objectClass} presence filter {@code (objectClass=*)}.
716     * <p>
717     * A call to this method is equivalent to but more efficient than the
718     * following code:
719     *
720     * <pre>
721     * Filter.present(&quot;objectClass&quot;);
722     * </pre>
723     *
724     * @return The {@code objectClass} presence filter {@code (objectClass=*)}.
725     */
726    public static Filter objectClassPresent() {
727        return OBJECT_CLASS_PRESENT;
728    }
729
730    /**
731     * Creates a new {@code or} filter using the provided list of sub-filters.
732     * <p>
733     * Creating a new {@code or} filter with a {@code null} or empty list of
734     * sub-filters is equivalent to calling {@link #alwaysFalse()}.
735     *
736     * @param subFilters
737     *            The list of sub-filters, may be empty or {@code null}.
738     * @return The newly created {@code or} filter.
739     */
740    public static Filter or(final Collection<Filter> subFilters) {
741        if (subFilters == null || subFilters.isEmpty()) {
742            // RFC 4526 - FALSE filter.
743            return alwaysFalse();
744        } else if (subFilters.size() == 1) {
745            final Filter subFilter = subFilters.iterator().next();
746            Reject.ifNull(subFilter);
747            return new Filter(new OrImpl(Collections.singletonList(subFilter)));
748        } else {
749            final List<Filter> subFiltersList = new ArrayList<>(subFilters.size());
750            for (final Filter subFilter : subFilters) {
751                Reject.ifNull(subFilter);
752                subFiltersList.add(subFilter);
753            }
754            return new Filter(new OrImpl(Collections.unmodifiableList(subFiltersList)));
755        }
756    }
757
758    /**
759     * Creates a new {@code or} filter using the provided list of sub-filters.
760     * <p>
761     * Creating a new {@code or} filter with a {@code null} or empty list of
762     * sub-filters is equivalent to calling {@link #alwaysFalse()}.
763     *
764     * @param subFilters
765     *            The list of sub-filters, may be empty or {@code null}.
766     * @return The newly created {@code or} filter.
767     */
768    public static Filter or(final Filter... subFilters) {
769        if (subFilters == null || subFilters.length == 0) {
770            // RFC 4526 - FALSE filter.
771            return alwaysFalse();
772        } else if (subFilters.length == 1) {
773            Reject.ifNull(subFilters[0]);
774            return new Filter(new OrImpl(Collections.singletonList(subFilters[0])));
775        } else {
776            final List<Filter> subFiltersList = new ArrayList<>(subFilters.length);
777            for (final Filter subFilter : subFilters) {
778                Reject.ifNull(subFilter);
779                subFiltersList.add(subFilter);
780            }
781            return new Filter(new OrImpl(Collections.unmodifiableList(subFiltersList)));
782        }
783    }
784
785    /**
786     * Creates a new {@code present} filter using the provided attribute
787     * description.
788     *
789     * @param attributeDescription
790     *            The attribute description.
791     * @return The newly created {@code present} filter.
792     */
793    public static Filter present(final String attributeDescription) {
794        Reject.ifNull(attributeDescription);
795        if ("objectclass".equals(toLowerCase(attributeDescription))) {
796            return OBJECT_CLASS_PRESENT;
797        }
798        return new Filter(new PresentImpl(attributeDescription));
799    }
800
801    /**
802     * Creates a new {@code substrings} filter using the provided attribute
803     * description, {@code initial}, {@code final}, and {@code any} sub-strings.
804     * <p>
805     * Any substrings which are not instances of {@code ByteString} will be
806     * converted using the {@link ByteString#valueOfObject(Object)} method.
807     *
808     * @param attributeDescription
809     *            The attribute description.
810     * @param initialSubstring
811     *            The initial sub-string, may be {@code null} if either
812     *            {@code finalSubstring} or {@code anySubstrings} are specified.
813     * @param anySubstrings
814     *            The final sub-string, may be {@code null} or empty if either
815     *            {@code finalSubstring} or {@code initialSubstring} are
816     *            specified.
817     * @param finalSubstring
818     *            The final sub-string, may be {@code null}, may be {@code null}
819     *            if either {@code initialSubstring} or {@code anySubstrings}
820     *            are specified.
821     * @return The newly created {@code substrings} filter.
822     */
823    public static Filter substrings(final String attributeDescription,
824            final Object initialSubstring, final Collection<?> anySubstrings,
825            final Object finalSubstring) {
826        Reject.ifNull(attributeDescription);
827        Reject.ifFalse(initialSubstring != null
828                || finalSubstring != null
829                || (anySubstrings != null && !anySubstrings.isEmpty()),
830                "at least one substring (initial, any or final) must be specified");
831
832        List<ByteString> anySubstringList;
833        if (anySubstrings == null || anySubstrings.isEmpty()) {
834            anySubstringList = Collections.emptyList();
835        } else if (anySubstrings.size() == 1) {
836            final Object anySubstring = anySubstrings.iterator().next();
837            Reject.ifNull(anySubstring);
838            anySubstringList = Collections.singletonList(ByteString.valueOfObject(anySubstring));
839        } else {
840            anySubstringList = new ArrayList<>(anySubstrings.size());
841            for (final Object anySubstring : anySubstrings) {
842                Reject.ifNull(anySubstring);
843
844                anySubstringList.add(ByteString.valueOfObject(anySubstring));
845            }
846            anySubstringList = Collections.unmodifiableList(anySubstringList);
847        }
848
849        return new Filter(new SubstringsImpl(attributeDescription,
850                initialSubstring != null ? ByteString.valueOfObject(initialSubstring) : null,
851                anySubstringList, finalSubstring != null ? ByteString.valueOfObject(finalSubstring)
852                        : null));
853    }
854
855    /**
856     * Creates a new {@code unrecognized} filter using the provided ASN1 filter
857     * tag and content. This type of filter should be used for filters which are
858     * not part of the standard filter definition.
859     *
860     * @param filterTag
861     *            The ASN.1 tag.
862     * @param filterBytes
863     *            The filter content.
864     * @return The newly created {@code unrecognized} filter.
865     */
866    public static Filter unrecognized(final byte filterTag, final ByteString filterBytes) {
867        Reject.ifNull(filterBytes);
868        return new Filter(new UnrecognizedImpl(filterTag, filterBytes));
869    }
870
871    /**
872     * Parses the provided LDAP string representation of a filter as a
873     * {@code Filter}.
874     *
875     * @param string
876     *            The LDAP string representation of a filter.
877     * @return The parsed {@code Filter}.
878     * @throws LocalizedIllegalArgumentException
879     *             If {@code string} is not a valid LDAP string representation
880     *             of a filter.
881     * @see #format(String, Object...)
882     */
883    public static Filter valueOf(final String string) {
884        Reject.ifNull(string);
885
886        // If the filter is enclosed in a pair of single quotes it
887        // is invalid (issue #1024).
888        if (string.length() > 1 && string.startsWith("'") && string.endsWith("'")) {
889            final LocalizableMessage message = ERR_LDAP_FILTER_ENCLOSED_IN_APOSTROPHES.get(string);
890            throw new LocalizedIllegalArgumentException(message);
891        }
892
893        try {
894            if (string.startsWith("(")) {
895                if (string.endsWith(")")) {
896                    return valueOf0(string, 1, string.length() - 1);
897                } else {
898                    final LocalizableMessage message =
899                            ERR_LDAP_FILTER_MISMATCHED_PARENTHESES.get(string, 1, string.length());
900                    throw new LocalizedIllegalArgumentException(message);
901                }
902            } else {
903                // We tolerate the top level filter component not being
904                // surrounded by parentheses.
905                return valueOf0(string, 0, string.length());
906            }
907        } catch (final LocalizedIllegalArgumentException liae) {
908            throw liae;
909        } catch (final Exception e) {
910            final LocalizableMessage message =
911                    ERR_LDAP_FILTER_UNCAUGHT_EXCEPTION.get(string, String.valueOf(e));
912            throw new LocalizedIllegalArgumentException(message);
913        }
914    }
915
916    /**
917     * Creates a new filter using the provided filter template and unescaped
918     * assertion values. This method first escapes each of the assertion values
919     * and then substitutes them into the template using
920     * {@link String#format(String, Object...)}. Finally, the formatted string
921     * is parsed as an LDAP filter using {@link #valueOf(String)}.
922     * <p>
923     * This method may be useful in cases where the structure of a filter is not
924     * known at compile time, for example, it may be obtained from a
925     * configuration file. Example usage:
926     *
927     * <pre>
928     * String template = &quot;(|(cn=%s)(uid=user.%s))&quot;;
929     * Filter filter = Filter.format(template, &quot;alice&quot;, 123);
930     * </pre>
931     *
932     * Any assertion values which are not instances of {@code ByteString} will
933     * be converted using the {@link ByteString#valueOfObject(Object)} method.
934     *
935     * @param template
936     *            The filter template.
937     * @param assertionValues
938     *            The assertion values to be substituted into the template.
939     * @return The formatted template parsed as a {@code Filter}.
940     * @throws LocalizedIllegalArgumentException
941     *             If the formatted template is not a valid LDAP string
942     *             representation of a filter.
943     * @see #escapeAssertionValue(Object)
944     */
945    public static Filter format(final String template, final Object... assertionValues) {
946        final String[] assertionValueStrings = new String[assertionValues.length];
947        for (int i = 0; i < assertionValues.length; i++) {
948            assertionValueStrings[i] = escapeAssertionValue(assertionValues[i]);
949        }
950        final String filterString = String.format(template, (Object[]) assertionValueStrings);
951        return valueOf(filterString);
952    }
953
954    /** Converts an assertion value to a substring filter. */
955    private static Filter assertionValue2SubstringFilter(final String filterString,
956            final String attrType, final int equalPos, final int endPos) {
957        // Get a binary representation of the value.
958        final byte[] valueBytes = getBytes(filterString.substring(equalPos, endPos));
959
960        // Find the locations of all the asterisks in the value. Also, check to
961        // see if there are any escaped values, since they will need special treatment.
962        boolean hasEscape = false;
963        final LinkedList<Integer> asteriskPositions = new LinkedList<>();
964        for (int i = 0; i < valueBytes.length; i++) {
965            if (valueBytes[i] == ASTERISK) {
966                asteriskPositions.add(i);
967            } else if (valueBytes[i] == BACKSLASH) {
968                hasEscape = true;
969            }
970        }
971
972        // If there were no asterisks, then this isn't a substring filter.
973        if (asteriskPositions.isEmpty()) {
974            final LocalizableMessage message =
975                    ERR_LDAP_FILTER_SUBSTRING_NO_ASTERISKS.get(filterString, equalPos + 1, endPos);
976            throw new LocalizedIllegalArgumentException(message);
977        }
978
979        // If the value starts with an asterisk, then there is no subInitial
980        // component. Otherwise, parse out the subInitial.
981        ByteString subInitial;
982        int firstPos = asteriskPositions.removeFirst();
983        if (firstPos == 0) {
984            subInitial = null;
985        } else if (hasEscape) {
986            final ByteStringBuilder buffer = new ByteStringBuilder(firstPos);
987            escapeHexChars(buffer, attrType, valueBytes, 0, firstPos, equalPos);
988            subInitial = buffer.toByteString();
989        } else {
990            subInitial = ByteString.wrap(valueBytes, 0, firstPos);
991        }
992
993        // Next, process through the rest of the asterisks to get the subAny values.
994        final ArrayList<ByteString> subAny = new ArrayList<>();
995        for (final int asteriskPos : asteriskPositions) {
996            final int length = asteriskPos - firstPos - 1;
997
998            if (hasEscape) {
999                final ByteStringBuilder buffer = new ByteStringBuilder(length);
1000                escapeHexChars(buffer, attrType, valueBytes, firstPos + 1, asteriskPos, equalPos);
1001                subAny.add(buffer.toByteString());
1002                buffer.clear();
1003            } else {
1004                subAny.add(ByteString.wrap(valueBytes, firstPos + 1, length));
1005            }
1006            firstPos = asteriskPos;
1007        }
1008
1009        // Finally, see if there is anything after the last asterisk, which
1010        // would be the subFinal value.
1011        ByteString subFinal;
1012        if (firstPos == (valueBytes.length - 1)) {
1013            subFinal = null;
1014        } else {
1015            final int length = valueBytes.length - firstPos - 1;
1016
1017            if (hasEscape) {
1018                final ByteStringBuilder buffer = new ByteStringBuilder(length);
1019                escapeHexChars(buffer, attrType, valueBytes, firstPos + 1, valueBytes.length,
1020                        equalPos);
1021                subFinal = buffer.toByteString();
1022            } else {
1023                subFinal = ByteString.wrap(valueBytes, firstPos + 1, length);
1024            }
1025        }
1026        return new Filter(new SubstringsImpl(attrType, subInitial, subAny, subFinal));
1027    }
1028
1029    private static void escapeHexChars(final ByteStringBuilder valueBuffer, final String string,
1030            final byte[] valueBytes, final int fromIndex, final int len, final int errorIndex) {
1031        for (int i = fromIndex; i < len; i++) {
1032            if (valueBytes[i] == BACKSLASH) {
1033                // The next two bytes must be the hex characters that comprise
1034                // the binary value.
1035                if (i + 2 >= valueBytes.length) {
1036                    final LocalizableMessage message =
1037                            ERR_LDAP_FILTER_INVALID_ESCAPED_BYTE.get(string, errorIndex + i + 1);
1038                    throw new LocalizedIllegalArgumentException(message);
1039                }
1040
1041                byte byteValue = 0;
1042                switch (valueBytes[++i]) {
1043                case 0x30: // '0'
1044                    break;
1045                case 0x31: // '1'
1046                    byteValue = (byte) 0x10;
1047                    break;
1048                case 0x32: // '2'
1049                    byteValue = (byte) 0x20;
1050                    break;
1051                case 0x33: // '3'
1052                    byteValue = (byte) 0x30;
1053                    break;
1054                case 0x34: // '4'
1055                    byteValue = (byte) 0x40;
1056                    break;
1057                case 0x35: // '5'
1058                    byteValue = (byte) 0x50;
1059                    break;
1060                case 0x36: // '6'
1061                    byteValue = (byte) 0x60;
1062                    break;
1063                case 0x37: // '7'
1064                    byteValue = (byte) 0x70;
1065                    break;
1066                case 0x38: // '8'
1067                    byteValue = (byte) 0x80;
1068                    break;
1069                case 0x39: // '9'
1070                    byteValue = (byte) 0x90;
1071                    break;
1072                case 0x41: // 'A'
1073                case 0x61: // 'a'
1074                    byteValue = (byte) 0xA0;
1075                    break;
1076                case 0x42: // 'B'
1077                case 0x62: // 'b'
1078                    byteValue = (byte) 0xB0;
1079                    break;
1080                case 0x43: // 'C'
1081                case 0x63: // 'c'
1082                    byteValue = (byte) 0xC0;
1083                    break;
1084                case 0x44: // 'D'
1085                case 0x64: // 'd'
1086                    byteValue = (byte) 0xD0;
1087                    break;
1088                case 0x45: // 'E'
1089                case 0x65: // 'e'
1090                    byteValue = (byte) 0xE0;
1091                    break;
1092                case 0x46: // 'F'
1093                case 0x66: // 'f'
1094                    byteValue = (byte) 0xF0;
1095                    break;
1096                default:
1097                    final LocalizableMessage message =
1098                            ERR_LDAP_FILTER_INVALID_ESCAPED_BYTE.get(string, errorIndex + i + 1);
1099                    throw new LocalizedIllegalArgumentException(message);
1100                }
1101
1102                switch (valueBytes[++i]) {
1103                case 0x30: // '0'
1104                    break;
1105                case 0x31: // '1'
1106                    byteValue |= 0x01;
1107                    break;
1108                case 0x32: // '2'
1109                    byteValue |= 0x02;
1110                    break;
1111                case 0x33: // '3'
1112                    byteValue |= 0x03;
1113                    break;
1114                case 0x34: // '4'
1115                    byteValue |= 0x04;
1116                    break;
1117                case 0x35: // '5'
1118                    byteValue |= 0x05;
1119                    break;
1120                case 0x36: // '6'
1121                    byteValue |= 0x06;
1122                    break;
1123                case 0x37: // '7'
1124                    byteValue |= 0x07;
1125                    break;
1126                case 0x38: // '8'
1127                    byteValue |= 0x08;
1128                    break;
1129                case 0x39: // '9'
1130                    byteValue |= 0x09;
1131                    break;
1132                case 0x41: // 'A'
1133                case 0x61: // 'a'
1134                    byteValue |= 0x0A;
1135                    break;
1136                case 0x42: // 'B'
1137                case 0x62: // 'b'
1138                    byteValue |= 0x0B;
1139                    break;
1140                case 0x43: // 'C'
1141                case 0x63: // 'c'
1142                    byteValue |= 0x0C;
1143                    break;
1144                case 0x44: // 'D'
1145                case 0x64: // 'd'
1146                    byteValue |= 0x0D;
1147                    break;
1148                case 0x45: // 'E'
1149                case 0x65: // 'e'
1150                    byteValue |= 0x0E;
1151                    break;
1152                case 0x46: // 'F'
1153                case 0x66: // 'f'
1154                    byteValue |= 0x0F;
1155                    break;
1156                default:
1157                    final LocalizableMessage message =
1158                            ERR_LDAP_FILTER_INVALID_ESCAPED_BYTE.get(string, errorIndex + i + 1);
1159                    throw new LocalizedIllegalArgumentException(message);
1160                }
1161
1162                valueBuffer.appendByte(byteValue);
1163            } else {
1164                valueBuffer.appendByte(valueBytes[i]);
1165            }
1166        }
1167    }
1168
1169    private static Filter valueOf0(final String string, final int beginIndex /* inclusive */,
1170            final int endIndex /* exclusive */) {
1171        if (beginIndex >= endIndex) {
1172            final LocalizableMessage message = ERR_LDAP_FILTER_STRING_NULL.get();
1173            throw new LocalizedIllegalArgumentException(message);
1174        }
1175
1176        final int index = beginIndex;
1177        final char c = string.charAt(index);
1178
1179        if (c == '&') {
1180            final List<Filter> subFilters = valueOfFilterList(string, index + 1, endIndex);
1181            if (subFilters.isEmpty()) {
1182                return alwaysTrue();
1183            } else {
1184                return new Filter(new AndImpl(subFilters));
1185            }
1186        } else if (c == '|') {
1187            final List<Filter> subFilters = valueOfFilterList(string, index + 1, endIndex);
1188            if (subFilters.isEmpty()) {
1189                return alwaysFalse();
1190            } else {
1191                return new Filter(new OrImpl(subFilters));
1192            }
1193        } else if (c == '!') {
1194            if ((string.charAt(index + 1) != '(') || (string.charAt(endIndex - 1) != ')')) {
1195                final LocalizableMessage message =
1196                        ERR_LDAP_FILTER_COMPOUND_MISSING_PARENTHESES.get(string, index,
1197                                endIndex - 1);
1198                throw new LocalizedIllegalArgumentException(message);
1199            }
1200            final List<Filter> subFilters = valueOfFilterList(string, index + 1, endIndex);
1201            if (subFilters.size() != 1) {
1202                final LocalizableMessage message =
1203                        ERR_LDAP_FILTER_NOT_EXACTLY_ONE.get(string, index, endIndex);
1204                throw new LocalizedIllegalArgumentException(message);
1205            }
1206            return new Filter(new NotImpl(subFilters.get(0)));
1207        } else {
1208            // It must be a simple filter. It must have an equal sign at some
1209            // point, so find it.
1210            final int equalPos = indexOf(string, index, endIndex);
1211            if (equalPos <= index) {
1212                final LocalizableMessage message =
1213                        ERR_LDAP_FILTER_NO_EQUAL_SIGN.get(string, index, endIndex);
1214                throw new LocalizedIllegalArgumentException(message);
1215            }
1216
1217            // Look at the character immediately before the equal sign,
1218            // because it may help determine the filter type.
1219            String attributeDescription;
1220            ByteString assertionValue;
1221
1222            switch (string.charAt(equalPos - 1)) {
1223            case '~':
1224                attributeDescription = valueOfAttributeDescription(string, index, equalPos - 1);
1225                assertionValue = valueOfAssertionValue(string, equalPos + 1, endIndex);
1226                return new Filter(new ApproxMatchImpl(attributeDescription, assertionValue));
1227            case '>':
1228                attributeDescription = valueOfAttributeDescription(string, index, equalPos - 1);
1229                assertionValue = valueOfAssertionValue(string, equalPos + 1, endIndex);
1230                return new Filter(new GreaterOrEqualImpl(attributeDescription, assertionValue));
1231            case '<':
1232                attributeDescription = valueOfAttributeDescription(string, index, equalPos - 1);
1233                assertionValue = valueOfAssertionValue(string, equalPos + 1, endIndex);
1234                return new Filter(new LessOrEqualImpl(attributeDescription, assertionValue));
1235            case ':':
1236                return valueOfExtensibleFilter(string, index, equalPos, endIndex);
1237            default:
1238                attributeDescription = valueOfAttributeDescription(string, index, equalPos);
1239                return valueOfGenericFilter(string, attributeDescription, equalPos + 1, endIndex);
1240            }
1241        }
1242    }
1243
1244    private static int indexOf(final String string, final int index, final int endIndex) {
1245        for (int i = index; i < endIndex; i++) {
1246            if (string.charAt(i) == '=') {
1247                return i;
1248            }
1249        }
1250        return -1;
1251    }
1252
1253    private static ByteString valueOfAssertionValue(final String string, final int startIndex,
1254            final int endIndex) {
1255        final byte[] valueBytes = getBytes(string.substring(startIndex, endIndex));
1256        if (hasEscape(valueBytes)) {
1257            final ByteStringBuilder valueBuffer = new ByteStringBuilder(valueBytes.length);
1258            escapeHexChars(valueBuffer, string, valueBytes, 0, valueBytes.length, startIndex);
1259            return valueBuffer.toByteString();
1260        } else {
1261            return ByteString.wrap(valueBytes);
1262        }
1263    }
1264
1265    private static boolean hasEscape(final byte[] valueBytes) {
1266        for (final byte valueByte : valueBytes) {
1267            if (valueByte == BACKSLASH) {
1268                return true;
1269            }
1270        }
1271        return false;
1272    }
1273
1274    private static String valueOfAttributeDescription(final String string, final int startIndex,
1275            final int endIndex) {
1276        // The part of the filter string before the equal sign should be the
1277        // attribute type. Make sure that the characters it contains are
1278        // acceptable for attribute types, including those allowed by
1279        // attribute name exceptions (ASCII letters and digits, the dash,
1280        // and the underscore). We also need to allow attribute options,
1281        // which includes the semicolon and the equal sign.
1282        final String attrType = string.substring(startIndex, endIndex);
1283        for (int i = 0; i < attrType.length(); i++) {
1284            switch (attrType.charAt(i)) {
1285            case '-':
1286            case '0':
1287            case '1':
1288            case '2':
1289            case '3':
1290            case '4':
1291            case '5':
1292            case '6':
1293            case '7':
1294            case '8':
1295            case '9':
1296            case ';':
1297            case '=':
1298            case 'A':
1299            case 'B':
1300            case 'C':
1301            case 'D':
1302            case 'E':
1303            case 'F':
1304            case 'G':
1305            case 'H':
1306            case 'I':
1307            case 'J':
1308            case 'K':
1309            case 'L':
1310            case 'M':
1311            case 'N':
1312            case 'O':
1313            case 'P':
1314            case 'Q':
1315            case 'R':
1316            case 'S':
1317            case 'T':
1318            case 'U':
1319            case 'V':
1320            case 'W':
1321            case 'X':
1322            case 'Y':
1323            case 'Z':
1324            case '_':
1325            case 'a':
1326            case 'b':
1327            case 'c':
1328            case 'd':
1329            case 'e':
1330            case 'f':
1331            case 'g':
1332            case 'h':
1333            case 'i':
1334            case 'j':
1335            case 'k':
1336            case 'l':
1337            case 'm':
1338            case 'n':
1339            case 'o':
1340            case 'p':
1341            case 'q':
1342            case 'r':
1343            case 's':
1344            case 't':
1345            case 'u':
1346            case 'v':
1347            case 'w':
1348            case 'x':
1349            case 'y':
1350            case 'z':
1351                // These are all OK.
1352                break;
1353
1354            case '.':
1355            case '/':
1356            case ':':
1357            case '<':
1358            case '>':
1359            case '?':
1360            case '@':
1361            case '[':
1362            case '\\':
1363            case ']':
1364            case '^':
1365            case '`':
1366                // These are not allowed, but they are explicitly called out
1367                // because they are included in the range of values between '-'
1368                // and 'z', and making sure all possible characters are included
1369                // can help make the switch statement more efficient. We'll fall
1370                // through to the default clause to reject them.
1371            default:
1372                final LocalizableMessage message =
1373                        ERR_LDAP_FILTER_INVALID_CHAR_IN_ATTR_TYPE.get(attrType, String
1374                                .valueOf(attrType.charAt(i)), i);
1375                throw new LocalizedIllegalArgumentException(message);
1376            }
1377        }
1378
1379        return attrType;
1380    }
1381
1382    private static Filter valueOfExtensibleFilter(final String string, final int startIndex,
1383            final int equalIndex, final int endIndex) {
1384        String attributeDescription = null;
1385        boolean dnAttributes = false;
1386        String matchingRule = null;
1387
1388        // Look at the first character. If it is a colon, then it must be
1389        // followed by either the string "dn" or the matching rule ID. If it
1390        // is not, then must be the attribute type.
1391        final String lowerLeftStr = toLowerCase(string.substring(startIndex, equalIndex));
1392        if (string.charAt(startIndex) == ':') {
1393            // See if it starts with ":dn". Otherwise, it much be the matching
1394            // rule ID.
1395            if (lowerLeftStr.startsWith(":dn:")) {
1396                dnAttributes = true;
1397
1398                if ((startIndex + 4) < (equalIndex - 1)) {
1399                    matchingRule = string.substring(startIndex + 4, equalIndex - 1);
1400                }
1401            } else {
1402                matchingRule = string.substring(startIndex + 1, equalIndex - 1);
1403            }
1404        } else {
1405            final int colonPos = string.indexOf(':', startIndex);
1406            if (colonPos < 0) {
1407                final LocalizableMessage message =
1408                        ERR_LDAP_FILTER_EXTENSIBLE_MATCH_NO_COLON.get(string, startIndex);
1409                throw new LocalizedIllegalArgumentException(message);
1410            }
1411
1412            attributeDescription = string.substring(startIndex, colonPos);
1413
1414            // If there is anything left, then it should be ":dn" and/or ":"
1415            // followed by the matching rule ID.
1416            if (colonPos < (equalIndex - 1)) {
1417                if (lowerLeftStr.startsWith(":dn:", colonPos - startIndex)) {
1418                    dnAttributes = true;
1419
1420                    if ((colonPos + 4) < (equalIndex - 1)) {
1421                        matchingRule = string.substring(colonPos + 4, equalIndex - 1);
1422                    }
1423                } else {
1424                    matchingRule = string.substring(colonPos + 1, equalIndex - 1);
1425                }
1426            }
1427        }
1428
1429        // Parse out the attribute value.
1430        final ByteString matchValue = valueOfAssertionValue(string, equalIndex + 1, endIndex);
1431
1432        // Make sure that the filter has at least one of an attribute
1433        // description and/or a matching rule ID.
1434        if (attributeDescription == null && matchingRule == null) {
1435            final LocalizableMessage message =
1436                    ERR_LDAP_FILTER_EXTENSIBLE_MATCH_NO_AD_OR_MR.get(string, startIndex);
1437            throw new LocalizedIllegalArgumentException(message);
1438        }
1439
1440        return new Filter(new ExtensibleMatchImpl(matchingRule, attributeDescription, matchValue,
1441                dnAttributes));
1442    }
1443
1444    private static List<Filter> valueOfFilterList(final String string, final int startIndex,
1445            final int endIndex) {
1446        // If the end index is equal to the start index, then there are no
1447        // components.
1448        if (startIndex >= endIndex) {
1449            return Collections.emptyList();
1450        }
1451
1452        // At least one sub-filter.
1453        Filter firstFilter = null;
1454        List<Filter> subFilters = null;
1455
1456        // The first and last characters must be parentheses. If not, then
1457        // that's an error.
1458        if ((string.charAt(startIndex) != '(') || (string.charAt(endIndex - 1) != ')')) {
1459            final LocalizableMessage message =
1460                    ERR_LDAP_FILTER_COMPOUND_MISSING_PARENTHESES.get(string, startIndex, endIndex);
1461            throw new LocalizedIllegalArgumentException(message);
1462        }
1463
1464        // Iterate through the characters in the value. Whenever an open
1465        // parenthesis is found, locate the corresponding close parenthesis
1466        // by counting the number of intermediate open/close parentheses.
1467        int pendingOpens = 0;
1468        int openIndex = -1;
1469        for (int i = startIndex; i < endIndex; i++) {
1470            final char c = string.charAt(i);
1471            if (c == '(') {
1472                if (openIndex < 0) {
1473                    openIndex = i;
1474                }
1475                pendingOpens++;
1476            } else if (c == ')') {
1477                pendingOpens--;
1478                if (pendingOpens == 0) {
1479                    final Filter subFilter = valueOf0(string, openIndex + 1, i);
1480                    if (subFilters != null) {
1481                        subFilters.add(subFilter);
1482                    } else if (firstFilter != null) {
1483                        subFilters = new LinkedList<>();
1484                        subFilters.add(firstFilter);
1485                        subFilters.add(subFilter);
1486                        firstFilter = null;
1487                    } else {
1488                        firstFilter = subFilter;
1489                    }
1490                    openIndex = -1;
1491                } else if (pendingOpens < 0) {
1492                    final LocalizableMessage message =
1493                            ERR_LDAP_FILTER_NO_CORRESPONDING_OPEN_PARENTHESIS.get(string, i);
1494                    throw new LocalizedIllegalArgumentException(message);
1495                }
1496            } else if (pendingOpens <= 0) {
1497                final LocalizableMessage message =
1498                        ERR_LDAP_FILTER_COMPOUND_MISSING_PARENTHESES.get(string, startIndex,
1499                                endIndex);
1500                throw new LocalizedIllegalArgumentException(message);
1501            }
1502        }
1503
1504        // At this point, we have parsed the entire set of filter
1505        // components. The list of open parenthesis positions must be empty.
1506        if (pendingOpens != 0) {
1507            final LocalizableMessage message =
1508                    ERR_LDAP_FILTER_NO_CORRESPONDING_CLOSE_PARENTHESIS.get(string, openIndex);
1509            throw new LocalizedIllegalArgumentException(message);
1510        }
1511
1512        if (subFilters != null) {
1513            return Collections.unmodifiableList(subFilters);
1514        } else {
1515            return Collections.singletonList(firstFilter);
1516        }
1517    }
1518
1519    private static Filter valueOfGenericFilter(final String string,
1520            final String attributeDescription, final int startIndex, final int endIndex) {
1521        final int asteriskIdx = string.indexOf('*', startIndex);
1522        if (startIndex >= endIndex) {
1523            // Equality filter with empty assertion value.
1524            return new Filter(new EqualityMatchImpl(attributeDescription, ByteString.empty()));
1525        } else if ((endIndex - startIndex == 1) && (string.charAt(startIndex) == '*')) {
1526            // Single asterisk is a present filter.
1527            return present(attributeDescription);
1528        } else if (asteriskIdx > 0 && asteriskIdx <= endIndex) {
1529            // Substring filter.
1530            return assertionValue2SubstringFilter(string, attributeDescription, startIndex,
1531                    endIndex);
1532        } else {
1533            // equality filter.
1534            final ByteString assertionValue = valueOfAssertionValue(string, startIndex, endIndex);
1535            return new Filter(new EqualityMatchImpl(attributeDescription, assertionValue));
1536        }
1537    }
1538
1539    /**
1540     * Appends a properly-cleaned version of the provided value to the given
1541     * builder so that it can be safely used in string representations of this
1542     * search filter. The formatting changes that may be performed will be in
1543     * compliance with the specification in RFC 2254.
1544     *
1545     * @param builder
1546     *            The builder to which the "safe" version of the value will be
1547     *            appended.
1548     * @param value
1549     *            The value to be appended to the builder.
1550     */
1551    private static void valueToFilterString(final StringBuilder builder, final ByteString value) {
1552        // Get the binary representation of the value and iterate through
1553        // it to see if there are any unsafe characters. If there are,
1554        // then escape them and replace them with a two-digit hex
1555        // equivalent.
1556        builder.ensureCapacity(builder.length() + value.length());
1557        for (int i = 0; i < value.length(); i++) {
1558            // TODO: this is a bit overkill - it will escape all non-ascii
1559            // chars!
1560            final byte b = value.byteAt(i);
1561            if (((b & 0x7F) != b) // Not 7-bit clean
1562                    || b <= 0x1F  // Below the printable character range
1563                    || b == 0x28  // Open parenthesis
1564                    || b == 0x29  // Close parenthesis
1565                    || b == ASTERISK
1566                    || b == BACKSLASH
1567                    || b == 0x7F  /* Delete character */) {
1568                builder.append('\\');
1569                builder.append(byteToHex(b));
1570            } else {
1571                builder.append((char) b);
1572            }
1573        }
1574    }
1575
1576    private final Impl pimpl;
1577
1578    private Filter(final Impl pimpl) {
1579        this.pimpl = pimpl;
1580    }
1581
1582    /**
1583     * Applies a {@code FilterVisitor} to this {@code Filter}.
1584     *
1585     * @param <R>
1586     *            The return type of the visitor's methods.
1587     * @param <P>
1588     *            The type of the additional parameters to the visitor's
1589     *            methods.
1590     * @param v
1591     *            The filter visitor.
1592     * @param p
1593     *            Optional additional visitor parameter.
1594     * @return A result as specified by the visitor.
1595     */
1596    public <R, P> R accept(final FilterVisitor<R, P> v, final P p) {
1597        return pimpl.accept(v, p);
1598    }
1599
1600    /**
1601     * Returns a {@code Matcher} which can be used to compare this
1602     * {@code Filter} against entries using the default schema.
1603     *
1604     * @return The {@code Matcher}.
1605     */
1606    public Matcher matcher() {
1607        return new Matcher(this, Schema.getDefaultSchema());
1608    }
1609
1610    /**
1611     * Returns a {@code Matcher} which can be used to compare this
1612     * {@code Filter} against entries using the provided {@code Schema}.
1613     *
1614     * @param schema
1615     *            The schema which the {@code Matcher} should use for
1616     *            comparisons.
1617     * @return The {@code Matcher}.
1618     */
1619    public Matcher matcher(final Schema schema) {
1620        return new Matcher(this, schema);
1621    }
1622
1623    /**
1624     * Indicates whether this {@code Filter} matches the provided {@code Entry}
1625     * using the default schema.
1626     * <p>
1627     * Calling this method is equivalent to the following:
1628     *
1629     * <pre>
1630     * matcher().matches(entry);
1631     * </pre>
1632     *
1633     * @param entry
1634     *            The entry to be matched.
1635     * @return The result of matching the provided {@code Entry} against this
1636     *         {@code Filter} using the default schema.
1637     */
1638    public ConditionResult matches(final Entry entry) {
1639        return matcher(Schema.getDefaultSchema()).matches(entry);
1640    }
1641
1642    /**
1643     * Returns a {@code String} whose contents is the LDAP string representation
1644     * of this {@code Filter}.
1645     *
1646     * @return The LDAP string representation of this {@code Filter}.
1647     */
1648    @Override
1649    public String toString() {
1650        final StringBuilder builder = new StringBuilder();
1651        return pimpl.accept(TO_STRING_VISITOR, builder).toString();
1652    }
1653}