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-2010 Sun Microsystems, Inc.
025 *      Portions copyright 2011-2015 ForgeRock AS
026 */
027package org.forgerock.opendj.ldap;
028
029import java.util.Arrays;
030import java.util.Iterator;
031import java.util.LinkedHashMap;
032import java.util.LinkedList;
033import java.util.List;
034import java.util.Map;
035import java.util.SortedSet;
036import java.util.TreeSet;
037import java.util.WeakHashMap;
038
039import org.forgerock.i18n.LocalizableMessage;
040import org.forgerock.i18n.LocalizedIllegalArgumentException;
041import org.forgerock.opendj.ldap.schema.AttributeType;
042import org.forgerock.opendj.ldap.schema.Schema;
043import org.forgerock.opendj.ldap.schema.UnknownSchemaElementException;
044import org.forgerock.util.Reject;
045
046import com.forgerock.opendj.util.ASCIICharProp;
047import com.forgerock.opendj.util.Iterators;
048
049import static org.forgerock.opendj.ldap.schema.SchemaOptions.*;
050
051import static com.forgerock.opendj.ldap.CoreMessages.*;
052import static com.forgerock.opendj.util.StaticUtils.*;
053
054/**
055 * An attribute description as defined in RFC 4512 section 2.5. Attribute
056 * descriptions are used to identify an attribute in an entry and are composed
057 * of an attribute type and a set of zero or more attribute options.
058 *
059 * @see <a href="http://tools.ietf.org/html/rfc4512#section-2.5">RFC 4512 -
060 *      Lightweight Directory Access Protocol (LDAP): Directory Information
061 *      Models </a>
062 */
063public final class AttributeDescription implements Comparable<AttributeDescription> {
064    private static abstract class Impl implements Iterable<String> {
065        protected Impl() {
066            // Nothing to do.
067        }
068
069        public abstract int compareTo(Impl other);
070
071        public abstract boolean hasOption(String normalizedOption);
072
073        public abstract boolean equals(Impl other);
074
075        public abstract String firstNormalizedOption();
076
077        @Override
078        public abstract int hashCode();
079
080        public abstract boolean hasOptions();
081
082        public abstract boolean isSubTypeOf(Impl other);
083
084        public abstract boolean isSuperTypeOf(Impl other);
085
086        public abstract int size();
087
088    }
089
090    private static final class MultiOptionImpl extends Impl {
091
092        private final String[] normalizedOptions;
093
094        private final String[] options;
095
096        private MultiOptionImpl(final String[] options, final String[] normalizedOptions) {
097            if (normalizedOptions.length < 2) {
098                throw new AssertionError();
099            }
100
101            this.options = options;
102            this.normalizedOptions = normalizedOptions;
103        }
104
105        @Override
106        public int compareTo(final Impl other) {
107            final int thisSize = normalizedOptions.length;
108            final int otherSize = other.size();
109
110            if (thisSize < otherSize) {
111                return -1;
112            } else if (thisSize > otherSize) {
113                return 1;
114            } else {
115                // Same number of options.
116                final MultiOptionImpl otherImpl = (MultiOptionImpl) other;
117                for (int i = 0; i < thisSize; i++) {
118                    final String o1 = normalizedOptions[i];
119                    final String o2 = otherImpl.normalizedOptions[i];
120                    final int result = o1.compareTo(o2);
121                    if (result != 0) {
122                        return result;
123                    }
124                }
125
126                // All options the same.
127                return 0;
128            }
129        }
130
131        @Override
132        public boolean hasOption(final String normalizedOption) {
133            final int sz = normalizedOptions.length;
134            for (int i = 0; i < sz; i++) {
135                if (normalizedOptions[i].equals(normalizedOption)) {
136                    return true;
137                }
138            }
139            return false;
140        }
141
142        @Override
143        public boolean equals(final Impl other) {
144            if (other instanceof MultiOptionImpl) {
145                final MultiOptionImpl tmp = (MultiOptionImpl) other;
146                return Arrays.equals(normalizedOptions, tmp.normalizedOptions);
147            } else {
148                return false;
149            }
150        }
151
152        @Override
153        public String firstNormalizedOption() {
154            return normalizedOptions[0];
155        }
156
157        @Override
158        public int hashCode() {
159            return Arrays.hashCode(normalizedOptions);
160        }
161
162        @Override
163        public boolean hasOptions() {
164            return true;
165        }
166
167        @Override
168        public boolean isSubTypeOf(final Impl other) {
169            // Must contain a super-set of other's options.
170            if (other == ZERO_OPTION_IMPL) {
171                return true;
172            } else if (other.size() == 1) {
173                return hasOption(other.firstNormalizedOption());
174            } else if (other.size() > size()) {
175                return false;
176            } else {
177                // Check this contains other's options.
178                //
179                // This could be optimized more if required, but it's probably
180                // not worth it.
181                final MultiOptionImpl tmp = (MultiOptionImpl) other;
182                for (final String normalizedOption : tmp.normalizedOptions) {
183                    if (!hasOption(normalizedOption)) {
184                        return false;
185                    }
186                }
187                return true;
188            }
189        }
190
191        @Override
192        public boolean isSuperTypeOf(final Impl other) {
193            // Must contain a sub-set of other's options.
194            for (final String normalizedOption : normalizedOptions) {
195                if (!other.hasOption(normalizedOption)) {
196                    return false;
197                }
198            }
199            return true;
200        }
201
202        public Iterator<String> iterator() {
203            return Iterators.arrayIterator(options);
204        }
205
206        @Override
207        public int size() {
208            return normalizedOptions.length;
209        }
210
211    }
212
213    private static final class SingleOptionImpl extends Impl {
214
215        private final String normalizedOption;
216
217        private final String option;
218
219        private SingleOptionImpl(final String option, final String normalizedOption) {
220            this.option = option;
221            this.normalizedOption = normalizedOption;
222        }
223
224        @Override
225        public int compareTo(final Impl other) {
226            if (other == ZERO_OPTION_IMPL) {
227                // If other has zero options then this sorts after.
228                return 1;
229            } else if (other.size() == 1) {
230                // Same number of options, so compare.
231                return normalizedOption.compareTo(other.firstNormalizedOption());
232            } else {
233                // Other has more options, so comes after.
234                return -1;
235            }
236        }
237
238        @Override
239        public boolean hasOption(final String normalizedOption) {
240            return this.normalizedOption.equals(normalizedOption);
241        }
242
243        @Override
244        public boolean equals(final Impl other) {
245            return other.size() == 1 && other.hasOption(normalizedOption);
246        }
247
248        @Override
249        public String firstNormalizedOption() {
250            return normalizedOption;
251        }
252
253        @Override
254        public int hashCode() {
255            return normalizedOption.hashCode();
256        }
257
258        @Override
259        public boolean hasOptions() {
260            return true;
261        }
262
263        @Override
264        public boolean isSubTypeOf(final Impl other) {
265            // Other must have no options or the same option.
266            return other == ZERO_OPTION_IMPL || equals(other);
267        }
268
269        @Override
270        public boolean isSuperTypeOf(final Impl other) {
271            // Other must have this option.
272            return other.hasOption(normalizedOption);
273        }
274
275        public Iterator<String> iterator() {
276            return Iterators.singletonIterator(option);
277        }
278
279        @Override
280        public int size() {
281            return 1;
282        }
283
284    }
285
286    private static final class ZeroOptionImpl extends Impl {
287        private ZeroOptionImpl() {
288            // Nothing to do.
289        }
290
291        @Override
292        public int compareTo(final Impl other) {
293            // If other has options then this sorts before.
294            return this == other ? 0 : -1;
295        }
296
297        @Override
298        public boolean hasOption(final String normalizedOption) {
299            return false;
300        }
301
302        @Override
303        public boolean equals(final Impl other) {
304            return this == other;
305        }
306
307        @Override
308        public String firstNormalizedOption() {
309            // No first option.
310            return null;
311        }
312
313        @Override
314        public int hashCode() {
315            // Use attribute type hash code.
316            return 0;
317        }
318
319        @Override
320        public boolean hasOptions() {
321            return false;
322        }
323
324        @Override
325        public boolean isSubTypeOf(final Impl other) {
326            // Can only be a sub-type if other has no options.
327            return this == other;
328        }
329
330        @Override
331        public boolean isSuperTypeOf(final Impl other) {
332            // Will always be a super-type.
333            return true;
334        }
335
336        public Iterator<String> iterator() {
337            return Iterators.emptyIterator();
338        }
339
340        @Override
341        public int size() {
342            return 0;
343        }
344
345    }
346
347    private static final ThreadLocal<WeakHashMap<Schema, Map<String, AttributeDescription>>> CACHE =
348            new ThreadLocal<WeakHashMap<Schema, Map<String, AttributeDescription>>>() {
349
350                /** {@inheritDoc} */
351                @Override
352                protected WeakHashMap<Schema, Map<String, AttributeDescription>> initialValue() {
353                    return new WeakHashMap<>();
354                }
355            };
356
357    /** Object class attribute description. */
358    private static final ZeroOptionImpl ZERO_OPTION_IMPL = new ZeroOptionImpl();
359
360    private static final AttributeDescription OBJECT_CLASS;
361    static {
362        final AttributeType attributeType = Schema.getCoreSchema().getAttributeType("2.5.4.0");
363        OBJECT_CLASS =
364                new AttributeDescription(attributeType.getNameOrOID(), attributeType,
365                        ZERO_OPTION_IMPL);
366    }
367
368    /**
369     * This is the size of the per-thread per-schema attribute description
370     * cache. We should be conservative here in case there are many
371     * threads.
372     */
373    private static final int ATTRIBUTE_DESCRIPTION_CACHE_SIZE = 512;
374
375    /**
376     * Returns an attribute description having the same attribute type and
377     * options as this attribute description as well as the provided option.
378     *
379     * @param option
380     *            The attribute option.
381     * @return The new attribute description containing {@code option}.
382     * @throws NullPointerException
383     *             If {@code attributeDescription} or {@code option} was
384     *             {@code null}.
385     */
386    public AttributeDescription withOption(final String option) {
387        Reject.ifNull(option);
388
389        final String normalizedOption = toLowerCase(option);
390        if (pimpl.hasOption(normalizedOption)) {
391            return this;
392        }
393
394        final String oldAttributeDescription = attributeDescription;
395        final StringBuilder builder =
396                new StringBuilder(oldAttributeDescription.length() + option.length() + 1);
397        builder.append(oldAttributeDescription);
398        builder.append(';');
399        builder.append(option);
400        final String newAttributeDescription = builder.toString();
401
402        final Impl impl = pimpl;
403        if (impl instanceof ZeroOptionImpl) {
404            return new AttributeDescription(newAttributeDescription, attributeType,
405                    new SingleOptionImpl(option, normalizedOption));
406        } else if (impl instanceof SingleOptionImpl) {
407            final SingleOptionImpl simpl = (SingleOptionImpl) impl;
408
409            final String[] newOptions = new String[2];
410            newOptions[0] = simpl.option;
411            newOptions[1] = option;
412
413            final String[] newNormalizedOptions = new String[2];
414            if (normalizedOption.compareTo(simpl.normalizedOption) < 0) {
415                newNormalizedOptions[0] = normalizedOption;
416                newNormalizedOptions[1] = simpl.normalizedOption;
417            } else {
418                newNormalizedOptions[0] = simpl.normalizedOption;
419                newNormalizedOptions[1] = normalizedOption;
420            }
421
422            return new AttributeDescription(newAttributeDescription, attributeType,
423                    new MultiOptionImpl(newOptions, newNormalizedOptions));
424        } else {
425            final MultiOptionImpl mimpl = (MultiOptionImpl) impl;
426
427            final int sz1 = mimpl.options.length;
428            final String[] newOptions = Arrays.copyOf(mimpl.options, sz1 + 1);
429            newOptions[sz1] = option;
430
431            final int sz2 = mimpl.normalizedOptions.length;
432            final String[] newNormalizedOptions = new String[sz2 + 1];
433            boolean inserted = false;
434            for (int i = 0; i < sz2; i++) {
435                if (!inserted) {
436                    final String s = mimpl.normalizedOptions[i];
437                    if (normalizedOption.compareTo(s) < 0) {
438                        newNormalizedOptions[i] = normalizedOption;
439                        newNormalizedOptions[i + 1] = s;
440                        inserted = true;
441                    } else {
442                        newNormalizedOptions[i] = s;
443                    }
444                } else {
445                    newNormalizedOptions[i + 1] = mimpl.normalizedOptions[i];
446                }
447            }
448
449            if (!inserted) {
450                newNormalizedOptions[sz2] = normalizedOption;
451            }
452
453            return new AttributeDescription(newAttributeDescription, attributeType,
454                    new MultiOptionImpl(newOptions, newNormalizedOptions));
455        }
456    }
457
458    /**
459     * Returns an attribute description having the same attribute type and
460     * options as this attribute description except for the provided option.
461     * <p>
462     * This method is idempotent: if this attribute description does not contain
463     * the provided option then this attribute description will be returned.
464     *
465     * @param option
466     *            The attribute option.
467     * @return The new attribute description excluding {@code option}.
468     * @throws NullPointerException
469     *             If {@code attributeDescription} or {@code option} was
470     *             {@code null}.
471     */
472    public AttributeDescription withoutOption(final String option) {
473        Reject.ifNull(option);
474
475        final String normalizedOption = toLowerCase(option);
476        if (!pimpl.hasOption(normalizedOption)) {
477            return this;
478        }
479
480        final String oldAttributeDescription = attributeDescription;
481        final StringBuilder builder =
482                new StringBuilder(oldAttributeDescription.length() - option.length() - 1);
483
484        final String normalizedOldAttributeDescription = toLowerCase(oldAttributeDescription);
485        final int index = normalizedOldAttributeDescription.indexOf(normalizedOption);
486        builder.append(oldAttributeDescription, 0, index - 1 /* to semi-colon */);
487        builder.append(oldAttributeDescription, index + option.length(), oldAttributeDescription
488                .length());
489        final String newAttributeDescription = builder.toString();
490
491        final Impl impl = pimpl;
492        if (impl instanceof ZeroOptionImpl) {
493            throw new IllegalStateException("ZeroOptionImpl unexpected");
494        } else if (impl instanceof SingleOptionImpl) {
495            return new AttributeDescription(newAttributeDescription, attributeType,
496                    ZERO_OPTION_IMPL);
497        } else {
498            final MultiOptionImpl mimpl = (MultiOptionImpl) impl;
499            if (mimpl.options.length == 2) {
500                final String remainingOption;
501                final String remainingNormalizedOption;
502
503                if (toLowerCase(mimpl.options[0]).equals(normalizedOption)) {
504                    remainingOption = mimpl.options[1];
505                } else {
506                    remainingOption = mimpl.options[0];
507                }
508
509                if (mimpl.normalizedOptions[0].equals(normalizedOption)) {
510                    remainingNormalizedOption = mimpl.normalizedOptions[1];
511                } else {
512                    remainingNormalizedOption = mimpl.normalizedOptions[0];
513                }
514
515                return new AttributeDescription(newAttributeDescription, attributeType,
516                        new SingleOptionImpl(remainingOption, remainingNormalizedOption));
517            } else {
518                final String[] newOptions = new String[mimpl.options.length - 1];
519                final String[] newNormalizedOptions =
520                        new String[mimpl.normalizedOptions.length - 1];
521
522                for (int i = 0, j = 0; i < mimpl.options.length; i++) {
523                    if (!toLowerCase(mimpl.options[i]).equals(normalizedOption)) {
524                        newOptions[j++] = mimpl.options[i];
525                    }
526                }
527
528                for (int i = 0, j = 0; i < mimpl.normalizedOptions.length; i++) {
529                    if (!mimpl.normalizedOptions[i].equals(normalizedOption)) {
530                        newNormalizedOptions[j++] = mimpl.normalizedOptions[i];
531                    }
532                }
533
534                return new AttributeDescription(newAttributeDescription, attributeType,
535                        new MultiOptionImpl(newOptions, newNormalizedOptions));
536            }
537        }
538    }
539
540    /**
541     * Creates an attribute description having the provided attribute type and
542     * no options.
543     *
544     * @param attributeType
545     *            The attribute type.
546     * @return The attribute description.
547     * @throws NullPointerException
548     *             If {@code attributeType} was {@code null}.
549     */
550    public static AttributeDescription create(final AttributeType attributeType) {
551        Reject.ifNull(attributeType);
552
553        // Use object identity in case attribute type does not come from
554        // core schema.
555        if (attributeType == OBJECT_CLASS.getAttributeType()) {
556            return OBJECT_CLASS;
557        } else {
558            return new AttributeDescription(attributeType.getNameOrOID(), attributeType,
559                    ZERO_OPTION_IMPL);
560        }
561    }
562
563    /**
564     * Creates an attribute description having the provided attribute type and
565     * single option.
566     *
567     * @param attributeType
568     *            The attribute type.
569     * @param option
570     *            The attribute option.
571     * @return The attribute description.
572     * @throws NullPointerException
573     *             If {@code attributeType} or {@code option} was {@code null}.
574     */
575    public static AttributeDescription create(final AttributeType attributeType, final String option) {
576        Reject.ifNull(attributeType, option);
577
578        final String oid = attributeType.getNameOrOID();
579        final StringBuilder builder = new StringBuilder(oid.length() + option.length() + 1);
580        builder.append(oid);
581        builder.append(';');
582        builder.append(option);
583        final String attributeDescription = builder.toString();
584        final String normalizedOption = toLowerCase(option);
585
586        return new AttributeDescription(attributeDescription, attributeType, new SingleOptionImpl(
587                option, normalizedOption));
588    }
589
590    /**
591     * Creates an attribute description having the provided attribute type and
592     * options.
593     *
594     * @param attributeType
595     *            The attribute type.
596     * @param options
597     *            The attribute options.
598     * @return The attribute description.
599     * @throws NullPointerException
600     *             If {@code attributeType} or {@code options} was {@code null}.
601     */
602    public static AttributeDescription create(final AttributeType attributeType,
603            final String... options) {
604        Reject.ifNull(attributeType);
605        Reject.ifNull(options);
606
607        switch (options.length) {
608        case 0:
609            return create(attributeType);
610        case 1:
611            return create(attributeType, options[0]);
612        default:
613            final String[] optionsList = new String[options.length];
614            final String[] normalizedOptions = new String[options.length];
615
616            final String oid = attributeType.getNameOrOID();
617            final StringBuilder builder =
618                    new StringBuilder(oid.length() + options[0].length() + options[1].length() + 2);
619            builder.append(oid);
620
621            int i = 0;
622            for (final String option : options) {
623                builder.append(';');
624                builder.append(option);
625                optionsList[i] = option;
626                final String normalizedOption = toLowerCase(option);
627                normalizedOptions[i++] = normalizedOption;
628            }
629            Arrays.sort(normalizedOptions);
630
631            final String attributeDescription = builder.toString();
632            return new AttributeDescription(attributeDescription, attributeType,
633                    new MultiOptionImpl(optionsList, normalizedOptions));
634        }
635
636    }
637
638    /**
639     * Returns an attribute description representing the object class attribute
640     * type with no options.
641     *
642     * @return The object class attribute description.
643     */
644    public static AttributeDescription objectClass() {
645        return OBJECT_CLASS;
646    }
647
648    /**
649     * Parses the provided LDAP string representation of an attribute
650     * description using the default schema.
651     *
652     * @param attributeDescription
653     *            The LDAP string representation of an attribute description.
654     * @return The parsed attribute description.
655     * @throws UnknownSchemaElementException
656     *             If {@code attributeDescription} contains an attribute type
657     *             which is not contained in the default schema and the schema
658     *             is strict.
659     * @throws LocalizedIllegalArgumentException
660     *             If {@code attributeDescription} is not a valid LDAP string
661     *             representation of an attribute description.
662     * @throws NullPointerException
663     *             If {@code attributeDescription} was {@code null}.
664     */
665    public static AttributeDescription valueOf(final String attributeDescription) {
666        return valueOf(attributeDescription, Schema.getDefaultSchema());
667    }
668
669    /**
670     * Parses the provided LDAP string representation of an attribute
671     * description using the provided schema.
672     *
673     * @param attributeDescription
674     *            The LDAP string representation of an attribute description.
675     * @param schema
676     *            The schema to use when parsing the attribute description.
677     * @return The parsed attribute description.
678     * @throws UnknownSchemaElementException
679     *             If {@code attributeDescription} contains an attribute type
680     *             which is not contained in the provided schema and the schema
681     *             is strict.
682     * @throws LocalizedIllegalArgumentException
683     *             If {@code attributeDescription} is not a valid LDAP string
684     *             representation of an attribute description.
685     * @throws NullPointerException
686     *             If {@code attributeDescription} or {@code schema} was
687     *             {@code null}.
688     */
689    @SuppressWarnings("serial")
690    public static AttributeDescription valueOf(final String attributeDescription,
691            final Schema schema) {
692        Reject.ifNull(attributeDescription, schema);
693
694        // First look up the attribute description in the cache.
695        final WeakHashMap<Schema, Map<String, AttributeDescription>> threadLocalMap = CACHE.get();
696        Map<String, AttributeDescription> schemaLocalMap = threadLocalMap.get(schema);
697
698        AttributeDescription ad = null;
699        if (schemaLocalMap == null) {
700            schemaLocalMap =
701                    new LinkedHashMap<String, AttributeDescription>(
702                            ATTRIBUTE_DESCRIPTION_CACHE_SIZE, 0.75f, true) {
703                        @Override
704                        protected boolean removeEldestEntry(
705                                final Map.Entry<String, AttributeDescription> eldest) {
706                            return size() > ATTRIBUTE_DESCRIPTION_CACHE_SIZE;
707                        }
708                    };
709            threadLocalMap.put(schema, schemaLocalMap);
710        } else {
711            ad = schemaLocalMap.get(attributeDescription);
712        }
713
714        // Cache miss: decode and cache.
715        if (ad == null) {
716            ad = valueOf0(attributeDescription, schema);
717            schemaLocalMap.put(attributeDescription, ad);
718        }
719
720        return ad;
721    }
722
723    private static int skipTrailingWhiteSpace(final String attributeDescription, int i,
724            final int length) {
725        char c;
726        while (i < length) {
727            c = attributeDescription.charAt(i);
728            if (c != ' ') {
729                final LocalizableMessage message =
730                        ERR_ATTRIBUTE_DESCRIPTION_INTERNAL_WHITESPACE.get(attributeDescription);
731                throw new LocalizedIllegalArgumentException(message);
732            }
733            i++;
734        }
735        return i;
736    }
737
738    /** Uncached valueOf implementation. */
739    private static AttributeDescription valueOf0(final String attributeDescription, final Schema schema) {
740        final boolean allowMalformedNamesAndOptions = schema.getOption(ALLOW_MALFORMED_NAMES_AND_OPTIONS);
741        int i = 0;
742        final int length = attributeDescription.length();
743        char c = 0;
744
745        // Skip leading white space.
746        while (i < length) {
747            c = attributeDescription.charAt(i);
748            if (c != ' ') {
749                break;
750            }
751            i++;
752        }
753
754        // If we're already at the end then the attribute description only
755        // contained whitespace.
756        if (i == length) {
757            final LocalizableMessage message =
758                    ERR_ATTRIBUTE_DESCRIPTION_EMPTY.get(attributeDescription);
759            throw new LocalizedIllegalArgumentException(message);
760        }
761
762        // Validate the first non-whitespace character.
763        ASCIICharProp cp = ASCIICharProp.valueOf(c);
764        if (cp == null) {
765            final LocalizableMessage message =
766                    ERR_ATTRIBUTE_DESCRIPTION_ILLEGAL_CHARACTER.get(attributeDescription, c, i);
767            throw new LocalizedIllegalArgumentException(message);
768        }
769
770        // Mark the attribute type start position.
771        final int attributeTypeStart = i;
772        if (cp.isLetter()) {
773            // Non-numeric OID: letter + zero or more keychars.
774            i++;
775            while (i < length) {
776                c = attributeDescription.charAt(i);
777
778                if (c == ';' || c == ' ') {
779                    break;
780                }
781
782                cp = ASCIICharProp.valueOf(c);
783                if (!cp.isKeyChar(allowMalformedNamesAndOptions)) {
784                    final LocalizableMessage message =
785                            ERR_ATTRIBUTE_DESCRIPTION_ILLEGAL_CHARACTER.get(attributeDescription,
786                                    c, i);
787                    throw new LocalizedIllegalArgumentException(message);
788                }
789                i++;
790            }
791
792            // (charAt(i) == ';' || c == ' ' || i == length)
793        } else if (cp.isDigit()) {
794            // Numeric OID: decimal digit + zero or more dots or decimals.
795            i++;
796            while (i < length) {
797                c = attributeDescription.charAt(i);
798                if (c == ';' || c == ' ') {
799                    break;
800                }
801
802                cp = ASCIICharProp.valueOf(c);
803                if (c != '.' && !cp.isDigit()) {
804                    final LocalizableMessage message =
805                            ERR_ATTRIBUTE_DESCRIPTION_ILLEGAL_CHARACTER.get(attributeDescription,
806                                    c, i);
807                    throw new LocalizedIllegalArgumentException(message);
808                }
809                i++;
810            }
811
812            // (charAt(i) == ';' || charAt(i) == ' ' || i == length)
813        } else {
814            final LocalizableMessage message =
815                    ERR_ATTRIBUTE_DESCRIPTION_ILLEGAL_CHARACTER.get(attributeDescription, c, i);
816            throw new LocalizedIllegalArgumentException(message);
817        }
818
819        // Skip trailing white space.
820        final int attributeTypeEnd = i;
821        if (c == ' ') {
822            i = skipTrailingWhiteSpace(attributeDescription, i + 1, length);
823        }
824
825        // Determine the portion of the string containing the attribute type
826        // name.
827        String oid;
828        if (attributeTypeStart == 0 && attributeTypeEnd == length) {
829            oid = attributeDescription;
830        } else {
831            oid = attributeDescription.substring(attributeTypeStart, attributeTypeEnd);
832        }
833
834        if (oid.length() == 0) {
835            final LocalizableMessage message =
836                    ERR_ATTRIBUTE_DESCRIPTION_NO_TYPE.get(attributeDescription);
837            throw new LocalizedIllegalArgumentException(message);
838        }
839
840        // Get the attribute type from the schema.
841        final AttributeType attributeType = schema.getAttributeType(oid);
842
843        // If we're already at the end of the attribute description then it
844        // does not contain any options.
845        if (i == length) {
846            // Use object identity in case attribute type does not come from
847            // core schema.
848            if (attributeType == OBJECT_CLASS.getAttributeType()
849                    && attributeDescription.equals(OBJECT_CLASS.toString())) {
850                return OBJECT_CLASS;
851            } else {
852                return new AttributeDescription(attributeDescription, attributeType,
853                        ZERO_OPTION_IMPL);
854            }
855        }
856
857        // At this point 'i' must point at a semi-colon.
858        i++;
859        StringBuilder builder = null;
860        int optionStart = i;
861        while (i < length) {
862            c = attributeDescription.charAt(i);
863            if (c == ' ' || c == ';') {
864                break;
865            }
866
867            cp = ASCIICharProp.valueOf(c);
868            if (!cp.isKeyChar(allowMalformedNamesAndOptions)) {
869                final LocalizableMessage message =
870                        ERR_ATTRIBUTE_DESCRIPTION_ILLEGAL_CHARACTER.get(attributeDescription, c, i);
871                throw new LocalizedIllegalArgumentException(message);
872            }
873
874            if (builder == null) {
875                if (cp.isUpperCase()) {
876                    // Need to normalize the option.
877                    builder = new StringBuilder(length - optionStart);
878                    builder.append(attributeDescription, optionStart, i);
879                    builder.append(cp.toLowerCase());
880                }
881            } else {
882                builder.append(cp.toLowerCase());
883            }
884            i++;
885        }
886
887        String option = attributeDescription.substring(optionStart, i);
888        String normalizedOption;
889        if (builder != null) {
890            normalizedOption = builder.toString();
891        } else {
892            normalizedOption = option;
893        }
894
895        if (option.length() == 0) {
896            final LocalizableMessage message =
897                    ERR_ATTRIBUTE_DESCRIPTION_EMPTY_OPTION.get(attributeDescription);
898            throw new LocalizedIllegalArgumentException(message);
899        }
900
901        // Skip trailing white space.
902        if (c == ' ') {
903            i = skipTrailingWhiteSpace(attributeDescription, i + 1, length);
904        }
905
906        // If we're already at the end of the attribute description then it
907        // only contains a single option.
908        if (i == length) {
909            return new AttributeDescription(attributeDescription, attributeType,
910                    new SingleOptionImpl(option, normalizedOption));
911        }
912
913        // Multiple options need sorting and duplicates removed - we could
914        // optimize a bit further here for 2 option attribute descriptions.
915        final List<String> options = new LinkedList<>();
916        options.add(option);
917
918        final SortedSet<String> normalizedOptions = new TreeSet<>();
919        normalizedOptions.add(normalizedOption);
920
921        while (i < length) {
922            // At this point 'i' must point at a semi-colon.
923            i++;
924            builder = null;
925            optionStart = i;
926            while (i < length) {
927                c = attributeDescription.charAt(i);
928                if (c == ' ' || c == ';') {
929                    break;
930                }
931
932                cp = ASCIICharProp.valueOf(c);
933                if (!cp.isKeyChar(allowMalformedNamesAndOptions)) {
934                    final LocalizableMessage message =
935                            ERR_ATTRIBUTE_DESCRIPTION_ILLEGAL_CHARACTER.get(attributeDescription,
936                                    c, i);
937                    throw new LocalizedIllegalArgumentException(message);
938                }
939
940                if (builder == null) {
941                    if (cp.isUpperCase()) {
942                        // Need to normalize the option.
943                        builder = new StringBuilder(length - optionStart);
944                        builder.append(attributeDescription, optionStart, i);
945                        builder.append(cp.toLowerCase());
946                    }
947                } else {
948                    builder.append(cp.toLowerCase());
949                }
950                i++;
951            }
952
953            option = attributeDescription.substring(optionStart, i);
954            if (builder != null) {
955                normalizedOption = builder.toString();
956            } else {
957                normalizedOption = option;
958            }
959
960            if (option.length() == 0) {
961                final LocalizableMessage message =
962                        ERR_ATTRIBUTE_DESCRIPTION_EMPTY_OPTION.get(attributeDescription);
963                throw new LocalizedIllegalArgumentException(message);
964            }
965
966            // Skip trailing white space.
967            if (c == ' ') {
968                i = skipTrailingWhiteSpace(attributeDescription, i + 1, length);
969            }
970
971            options.add(option);
972            normalizedOptions.add(normalizedOption);
973        }
974
975        return new AttributeDescription(attributeDescription, attributeType, new MultiOptionImpl(
976                options.toArray(new String[options.size()]), normalizedOptions
977                        .toArray(new String[normalizedOptions.size()])));
978    }
979
980    private final String attributeDescription;
981
982    private final AttributeType attributeType;
983
984    private final Impl pimpl;
985
986    /** Private constructor. */
987    private AttributeDescription(final String attributeDescription,
988            final AttributeType attributeType, final Impl pimpl) {
989        this.attributeDescription = attributeDescription;
990        this.attributeType = attributeType;
991        this.pimpl = pimpl;
992    }
993
994    /**
995     * Compares this attribute description to the provided attribute
996     * description. The attribute types are compared first and then, if equal,
997     * the options are normalized, sorted, and compared.
998     *
999     * @param other
1000     *            The attribute description to be compared.
1001     * @return A negative integer, zero, or a positive integer as this attribute
1002     *         description is less than, equal to, or greater than the specified
1003     *         attribute description.
1004     * @throws NullPointerException
1005     *             If {@code name} was {@code null}.
1006     */
1007    public int compareTo(final AttributeDescription other) {
1008        final int result = attributeType.compareTo(other.attributeType);
1009        if (result != 0) {
1010            return result;
1011        } else {
1012            // Attribute type is the same, so compare options.
1013            return pimpl.compareTo(other.pimpl);
1014        }
1015    }
1016
1017    /**
1018     * Indicates whether or not this attribute description contains the provided
1019     * option.
1020     *
1021     * @param option
1022     *            The option for which to make the determination.
1023     * @return {@code true} if this attribute description has the provided
1024     *         option, or {@code false} if not.
1025     * @throws NullPointerException
1026     *             If {@code option} was {@code null}.
1027     */
1028    public boolean hasOption(final String option) {
1029        final String normalizedOption = toLowerCase(option);
1030        return pimpl.hasOption(normalizedOption);
1031    }
1032
1033    /**
1034     * Indicates whether the provided object is an attribute description which
1035     * is equal to this attribute description. It will be considered equal if
1036     * the attribute types are {@link AttributeType#equals equal} and normalized
1037     * sorted list of options are identical.
1038     *
1039     * @param o
1040     *            The object for which to make the determination.
1041     * @return {@code true} if the provided object is an attribute description
1042     *         that is equal to this attribute description, or {@code false} if
1043     *         not.
1044     */
1045    @Override
1046    public boolean equals(final Object o) {
1047        if (this == o) {
1048            return true;
1049        } else if (o instanceof AttributeDescription) {
1050            final AttributeDescription other = (AttributeDescription) o;
1051            return attributeType.equals(other.attributeType) && pimpl.equals(other.pimpl);
1052        } else {
1053            return false;
1054        }
1055    }
1056
1057    /**
1058     * Returns the attribute type associated with this attribute description.
1059     *
1060     * @return The attribute type associated with this attribute description.
1061     */
1062    public AttributeType getAttributeType() {
1063        return attributeType;
1064    }
1065
1066    /**
1067     * Returns an {@code Iterable} containing the options contained in this
1068     * attribute description. Attempts to remove options using an iterator's
1069     * {@code remove()} method are not permitted and will result in an
1070     * {@code UnsupportedOperationException} being thrown.
1071     *
1072     * @return An {@code Iterable} containing the options.
1073     */
1074    public Iterable<String> getOptions() {
1075        return pimpl;
1076    }
1077
1078    /**
1079     * Returns the hash code for this attribute description. It will be
1080     * calculated as the sum of the hash codes of the attribute type and
1081     * normalized sorted list of options.
1082     *
1083     * @return The hash code for this attribute description.
1084     */
1085    @Override
1086    public int hashCode() {
1087        // FIXME: should we cache this?
1088        return attributeType.hashCode() * 31 + pimpl.hashCode();
1089    }
1090
1091    /**
1092     * Indicates whether or not this attribute description has any options.
1093     *
1094     * @return {@code true} if this attribute description has any options, or
1095     *         {@code false} if not.
1096     */
1097    public boolean hasOptions() {
1098        return pimpl.hasOptions();
1099    }
1100
1101    /**
1102     * Indicates whether or not this attribute description is the
1103     * {@code objectClass} attribute description with no options.
1104     *
1105     * @return {@code true} if this attribute description is the
1106     *         {@code objectClass} attribute description with no options, or
1107     *         {@code false} if not.
1108     */
1109    public boolean isObjectClass() {
1110        return attributeType.isObjectClass() && !hasOptions();
1111    }
1112
1113    /**
1114     * Indicates whether this attribute description is a temporary place-holder
1115     * allocated dynamically by a non-strict schema when no corresponding
1116     * registered attribute type was found.
1117     * <p>
1118     * Place holder attribute descriptions have an attribute type whose OID is
1119     * the normalized attribute name with the string {@code -oid} appended. In
1120     * addition, they will use the directory string syntax and case ignore
1121     * matching rule.
1122     *
1123     * @return {@code true} if this is a temporary place-holder attribute
1124     *         description allocated dynamically by a non-strict schema when no
1125     *         corresponding registered attribute type was found.
1126     * @see Schema#getAttributeType(String)
1127     * @see AttributeType#isPlaceHolder()
1128     */
1129    public boolean isPlaceHolder() {
1130        return attributeType.isPlaceHolder();
1131    }
1132
1133    /**
1134     * Indicates whether or not this attribute description is a sub-type of the
1135     * provided attribute description as defined in RFC 4512 section 2.5.
1136     * Specifically, this method will return {@code true} if and only if the
1137     * following conditions are both {@code true}:
1138     * <ul>
1139     * <li>This attribute description has an attribute type which
1140     * {@link AttributeType#matches matches}, or is a sub-type of, the attribute
1141     * type in the provided attribute description.
1142     * <li>This attribute description contains all of the options contained in
1143     * the provided attribute description.
1144     * </ul>
1145     * Note that this method will return {@code true} if this attribute
1146     * description is equal to the provided attribute description.
1147     *
1148     * @param other
1149     *            The attribute description for which to make the determination.
1150     * @return {@code true} if this attribute description is a sub-type of the
1151     *         provided attribute description, or {@code false} if not.
1152     * @throws NullPointerException
1153     *             If {@code name} was {@code null}.
1154     */
1155    public boolean isSubTypeOf(final AttributeDescription other) {
1156        return attributeType.isSubTypeOf(other.attributeType)
1157            && pimpl.isSubTypeOf(other.pimpl);
1158    }
1159
1160    /**
1161     * Indicates whether or not this attribute description is a super-type of
1162     * the provided attribute description as defined in RFC 4512 section 2.5.
1163     * Specifically, this method will return {@code true} if and only if the
1164     * following conditions are both {@code true}:
1165     * <ul>
1166     * <li>This attribute description has an attribute type which
1167     * {@link AttributeType#matches matches}, or is a super-type of, the
1168     * attribute type in the provided attribute description.
1169     * <li>This attribute description contains a sub-set of the options
1170     * contained in the provided attribute description.
1171     * </ul>
1172     * Note that this method will return {@code true} if this attribute
1173     * description is equal to the provided attribute description.
1174     *
1175     * @param other
1176     *            The attribute description for which to make the determination.
1177     * @return {@code true} if this attribute description is a super-type of the
1178     *         provided attribute description, or {@code false} if not.
1179     * @throws NullPointerException
1180     *             If {@code name} was {@code null}.
1181     */
1182    public boolean isSuperTypeOf(final AttributeDescription other) {
1183        return attributeType.isSuperTypeOf(other.attributeType)
1184            && pimpl.isSuperTypeOf(other.pimpl);
1185    }
1186
1187    /**
1188     * Indicates whether the provided attribute description matches this
1189     * attribute description. It will be considered a match if the attribute
1190     * types {@link AttributeType#matches match} and the normalized sorted list
1191     * of options are identical.
1192     *
1193     * @param other
1194     *            The attribute description for which to make the determination.
1195     * @return {@code true} if the provided attribute description matches this
1196     *         attribute description, or {@code false} if not.
1197     */
1198    public boolean matches(final AttributeDescription other) {
1199        if (this == other) {
1200            return true;
1201        } else {
1202            return attributeType.matches(other.attributeType) && pimpl.equals(other.pimpl);
1203        }
1204    }
1205
1206    /**
1207     * Returns the string representation of this attribute description as
1208     * defined in RFC4512 section 2.5.
1209     *
1210     * @return The string representation of this attribute description.
1211     */
1212    @Override
1213    public String toString() {
1214        return attributeDescription;
1215    }
1216}