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