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.Map;
033import java.util.NoSuchElementException;
034import java.util.WeakHashMap;
035
036import org.forgerock.i18n.LocalizableMessage;
037import org.forgerock.i18n.LocalizedIllegalArgumentException;
038import org.forgerock.opendj.ldap.schema.CoreSchema;
039import org.forgerock.opendj.ldap.schema.Schema;
040import org.forgerock.opendj.ldap.schema.UnknownSchemaElementException;
041import org.forgerock.util.Reject;
042
043import com.forgerock.opendj.util.SubstringReader;
044
045import static com.forgerock.opendj.ldap.CoreMessages.*;
046import static com.forgerock.opendj.util.StaticUtils.*;
047
048/**
049 * A distinguished name (DN) as defined in RFC 4512 section 2.3 is the
050 * concatenation of its relative distinguished name (RDN) and its immediate
051 * superior's DN. A DN unambiguously refers to an entry in the Directory.
052 * <p>
053 * The following are examples of string representations of DNs:
054 *
055 * <pre>
056 * UID=nobody@example.com,DC=example,DC=com CN=John
057 * Smith,OU=Sales,O=ACME Limited,L=Moab,ST=Utah,C=US
058 * </pre>
059 *
060 * @see <a href="http://tools.ietf.org/html/rfc4512#section-2.3">RFC 4512 -
061 *      Lightweight Directory Access Protocol (LDAP): Directory Information
062 *      Models </a>
063 */
064public final class DN implements Iterable<RDN>, Comparable<DN> {
065
066    static final byte NORMALIZED_RDN_SEPARATOR = 0x00;
067    static final byte NORMALIZED_AVA_SEPARATOR = 0x01;
068    static final byte NORMALIZED_ESC_BYTE = 0x02;
069
070    private static final DN ROOT_DN = new DN(CoreSchema.getInstance(), null, null, "");
071
072    /**
073     * This is the size of the per-thread per-schema DN cache. We should
074     * be conservative here in case there are many threads. We will only
075     * cache parent DNs, so there's no need for it to be big.
076     */
077    private static final int DN_CACHE_SIZE = 32;
078
079    private static final ThreadLocal<WeakHashMap<Schema, Map<String, DN>>> CACHE =
080            new ThreadLocal<WeakHashMap<Schema, Map<String, DN>>>() {
081
082                /** {@inheritDoc} */
083                @Override
084                protected WeakHashMap<Schema, Map<String, DN>> initialValue() {
085                    return new WeakHashMap<>();
086                }
087            };
088
089    /**
090     * Returns the LDAP string representation of the provided DN attribute value
091     * in a form suitable for substitution directly into a DN string. This
092     * method may be useful in cases where a DN is to be constructed from a DN
093     * template using {@code String#format(String, Object...)}. The following
094     * example illustrates two approaches to constructing a DN:
095     *
096     * <pre>
097     * // This may contain user input.
098     * String attributeValue = ...;
099     *
100     * // Using the equality filter constructor:
101     * DN dn = DN.valueOf("ou=people,dc=example,dc=com").child("uid", attributeValue);
102     *
103     * // Using a String template:
104     * String dnTemplate = "uid=%s,ou=people,dc=example,dc=com";
105     * String dnString = String.format(dnTemplate,
106     *                                 DN.escapeAttributeValue(attributeValue));
107     * DN dn = DN.valueOf(dnString);
108     * </pre>
109     *
110     * <b>Note:</b> attribute values do not and should not be escaped before
111     * passing them to constructors like {@link #child(String, Object)}.
112     * Escaping is only required when creating DN strings.
113     *
114     * @param attributeValue
115     *            The attribute value.
116     * @return The LDAP string representation of the provided filter assertion
117     *         value in a form suitable for substitution directly into a filter
118     *         string.
119     */
120    public static String escapeAttributeValue(final Object attributeValue) {
121        Reject.ifNull(attributeValue);
122        final String s = String.valueOf(attributeValue);
123        final StringBuilder builder = new StringBuilder(s.length());
124        AVA.escapeAttributeValue(s, builder);
125        return builder.toString();
126    }
127
128    /**
129     * Creates a new DN using the provided DN template and unescaped attribute
130     * values using the default schema. This method first escapes each of the
131     * attribute values and then substitutes them into the template using
132     * {@link String#format(String, Object...)}. Finally, the formatted string
133     * is parsed as an LDAP DN using {@link #valueOf(String)}.
134     * <p>
135     * This method may be useful in cases where the structure of a DN is not
136     * known at compile time, for example, it may be obtained from a
137     * configuration file. Example usage:
138     *
139     * <pre>
140     * String template = &quot;uid=%s,ou=people,dc=example,dc=com&quot;;
141     * DN dn = DN.format(template, &quot;bjensen&quot;);
142     * </pre>
143     *
144     * @param template
145     *            The DN template.
146     * @param attributeValues
147     *            The attribute values to be substituted into the template.
148     * @return The formatted template parsed as a {@code DN}.
149     * @throws LocalizedIllegalArgumentException
150     *             If the formatted template is not a valid LDAP string
151     *             representation of a DN.
152     * @see #escapeAttributeValue(Object)
153     */
154    public static DN format(final String template, final Object... attributeValues) {
155        return format(template, Schema.getDefaultSchema(), attributeValues);
156    }
157
158    /**
159     * Creates a new DN using the provided DN template and unescaped attribute
160     * values using the provided schema. This method first escapes each of the
161     * attribute values and then substitutes them into the template using
162     * {@link String#format(String, Object...)}. Finally, the formatted string
163     * is parsed as an LDAP DN using {@link #valueOf(String)}.
164     * <p>
165     * This method may be useful in cases where the structure of a DN is not
166     * known at compile time, for example, it may be obtained from a
167     * configuration file. Example usage:
168     *
169     * <pre>
170     * String template = &quot;uid=%s,ou=people,dc=example,dc=com&quot;;
171     * DN dn = DN.format(template, &quot;bjensen&quot;);
172     * </pre>
173     *
174     * @param template
175     *            The DN template.
176     * @param schema
177     *            The schema to use when parsing the DN.
178     * @param attributeValues
179     *            The attribute values to be substituted into the template.
180     * @return The formatted template parsed as a {@code DN}.
181     * @throws LocalizedIllegalArgumentException
182     *             If the formatted template is not a valid LDAP string
183     *             representation of a DN.
184     * @see #escapeAttributeValue(Object)
185     */
186    public static DN format(final String template, final Schema schema,
187            final Object... attributeValues) {
188        final String[] attributeValueStrings = new String[attributeValues.length];
189        for (int i = 0; i < attributeValues.length; i++) {
190            attributeValueStrings[i] = escapeAttributeValue(attributeValues[i]);
191        }
192        final String dnString = String.format(template, (Object[]) attributeValueStrings);
193        return valueOf(dnString, schema);
194    }
195
196    /**
197     * Returns the Root DN. The Root DN does not contain and RDN components and
198     * is superior to all other DNs.
199     *
200     * @return The Root DN.
201     */
202    public static DN rootDN() {
203        return ROOT_DN;
204    }
205
206    /**
207     * Parses the provided LDAP string representation of a DN using the default
208     * schema.
209     *
210     * @param dn
211     *            The LDAP string representation of a DN.
212     * @return The parsed DN.
213     * @throws LocalizedIllegalArgumentException
214     *             If {@code dn} is not a valid LDAP string representation of a
215     *             DN.
216     * @throws NullPointerException
217     *             If {@code dn} was {@code null}.
218     * @see #format(String, Object...)
219     */
220    public static DN valueOf(final String dn) {
221        return valueOf(dn, Schema.getDefaultSchema());
222    }
223
224    /**
225     * Parses the provided LDAP string representation of a DN using the provided
226     * schema.
227     *
228     * @param dn
229     *            The LDAP string representation of a DN.
230     * @param schema
231     *            The schema to use when parsing the DN.
232     * @return The parsed DN.
233     * @throws LocalizedIllegalArgumentException
234     *             If {@code dn} is not a valid LDAP string representation of a
235     *             DN.
236     * @throws NullPointerException
237     *             If {@code dn} or {@code schema} was {@code null}.
238     * @see #format(String, Schema, Object...)
239     */
240    public static DN valueOf(final String dn, final Schema schema) {
241        Reject.ifNull(dn, schema);
242        if (dn.length() == 0) {
243            return ROOT_DN;
244        }
245
246        // First check if DN is already cached.
247        final Map<String, DN> cache = getCache(schema);
248        final DN cachedDN = cache.get(dn);
249        if (cachedDN != null) {
250            return cachedDN;
251        }
252
253        // Not in cache so decode.
254        final SubstringReader reader = new SubstringReader(dn);
255        return decode(dn, reader, schema, cache);
256    }
257
258    /**
259     * Compares the provided DN values to determine their relative order in a
260     * sorted list. The order is the natural order as defined by the
261     * {@code toNormalizedByteString()} method.
262     *
263     * @param dn1
264     *            The first DN to be compared. It must not be {@code null}.
265     * @param dn2
266     *            The second DN to be compared. It must not be {@code null}.
267     * @return A negative integer if the first DN should come before the second
268     *         DN in a sorted list, a positive integer if the first DN should
269     *         come after the second DN in a sorted list, or zero if the two DN
270     *         values can be considered equal.
271     */
272    private static int compareTo(final DN dn1, final DN dn2) {
273        return dn1.toNormalizedByteString().compareTo(dn2.toNormalizedByteString());
274    }
275
276    /** Decodes a DN using the provided reader and schema. */
277    private static DN decode(final String dnString, final SubstringReader reader,
278            final Schema schema, final Map<String, DN> cache) {
279        reader.skipWhitespaces();
280        if (reader.remaining() == 0) {
281            return ROOT_DN;
282        }
283
284        RDN rdn;
285        try {
286            rdn = RDN.decode(null, reader, schema);
287        } catch (final UnknownSchemaElementException e) {
288            final LocalizableMessage message =
289                    ERR_DN_TYPE_NOT_FOUND.get(reader.getString(), e.getMessageObject());
290            throw new LocalizedIllegalArgumentException(message);
291        }
292
293        DN parent;
294        if (reader.remaining() > 0 && reader.read() == ',') {
295            reader.mark();
296            final String parentString = reader.read(reader.remaining());
297
298            parent = cache.get(parentString);
299            if (parent == null) {
300                reader.reset();
301                parent = decode(parentString, reader, schema, cache);
302
303                // Only cache parent DNs since leaf DNs are likely to make the
304                // cache to volatile.
305                cache.put(parentString, parent);
306            }
307        } else {
308            parent = ROOT_DN;
309        }
310
311        return new DN(schema, parent, rdn, dnString);
312    }
313
314    @SuppressWarnings("serial")
315    private static Map<String, DN> getCache(final Schema schema) {
316        final WeakHashMap<Schema, Map<String, DN>> threadLocalMap = CACHE.get();
317        Map<String, DN> schemaLocalMap = threadLocalMap.get(schema);
318
319        if (schemaLocalMap == null) {
320            schemaLocalMap = new LinkedHashMap<String, DN>(DN_CACHE_SIZE, 0.75f, true) {
321                @Override
322                protected boolean removeEldestEntry(final Map.Entry<String, DN> e) {
323                    return size() > DN_CACHE_SIZE;
324                }
325            };
326            threadLocalMap.put(schema, schemaLocalMap);
327        }
328        return schemaLocalMap;
329    }
330
331    private final RDN rdn;
332
333    private DN parent;
334
335    private final int size;
336
337    /**
338     * The normalized byte string representation of this DN, which is not
339     * a valid DN and is not reversible to a valid DN.
340     */
341    private ByteString normalizedDN;
342
343    /**
344     * We need to store the original string value if provided in order to
345     * preserve the original whitespace.
346     */
347    private String stringValue;
348
349    /** The schema used to create this DN. */
350    private final Schema schema;
351
352    /** Private constructor. */
353    private DN(final Schema schema, final DN parent, final RDN rdn, final String stringValue) {
354        this(schema, parent, rdn, stringValue, parent != null ? parent.size + 1 : 0);
355    }
356
357    /** Private constructor. */
358    private DN(final Schema schema, final DN parent, final RDN rdn, final String stringValue, final int size) {
359        this.schema = schema;
360        this.parent = parent;
361        this.rdn = rdn;
362        this.stringValue = stringValue;
363        this.size = size;
364    }
365
366    /**
367     * Returns a DN which is subordinate to this DN and having the additional
368     * RDN components contained in the provided DN.
369     *
370     * @param dn
371     *            The DN containing the RDN components to be added to this DN.
372     * @return The subordinate DN.
373     * @throws NullPointerException
374     *             If {@code dn} was {@code null}.
375     */
376    public DN child(final DN dn) {
377        Reject.ifNull(dn);
378
379        if (dn.isRootDN()) {
380            return this;
381        } else if (isRootDN()) {
382            return dn;
383        } else {
384            final RDN[] rdns = new RDN[dn.size()];
385            int i = rdns.length;
386            for (DN next = dn; next.rdn != null; next = next.parent) {
387                rdns[--i] = next.rdn;
388            }
389            DN newDN = this;
390            for (i = 0; i < rdns.length; i++) {
391                newDN = new DN(this.schema, newDN, rdns[i], null);
392            }
393            return newDN;
394        }
395    }
396
397    /**
398     * Returns a DN which is an immediate child of this DN and having the
399     * specified RDN.
400     * <p>
401     * <b>Note:</b> the child DN whose RDN is {@link RDN#maxValue()} compares
402     * greater than all other possible child DNs, and may be used to construct
403     * range queries against DN keyed sorted collections such as
404     * {@code SortedSet} and {@code SortedMap}.
405     *
406     * @param rdn
407     *            The RDN for the child DN.
408     * @return The child DN.
409     * @throws NullPointerException
410     *             If {@code rdn} was {@code null}.
411     * @see RDN#maxValue()
412     */
413    public DN child(final RDN rdn) {
414        Reject.ifNull(rdn);
415        return new DN(this.schema, this, rdn, null);
416    }
417
418    /**
419     * Returns a DN which is subordinate to this DN and having the additional
420     * RDN components contained in the provided DN decoded using the default
421     * schema.
422     *
423     * @param dn
424     *            The DN containing the RDN components to be added to this DN.
425     * @return The subordinate DN.
426     * @throws LocalizedIllegalArgumentException
427     *             If {@code dn} is not a valid LDAP string representation of a
428     *             DN.
429     * @throws NullPointerException
430     *             If {@code dn} was {@code null}.
431     */
432    public DN child(final String dn) {
433        Reject.ifNull(dn);
434        return child(valueOf(dn));
435    }
436
437    /**
438     * Returns a DN which is an immediate child of this DN and with an RDN
439     * having the provided attribute type and value decoded using the default
440     * schema.
441     * <p>
442     * If {@code attributeValue} is not an instance of {@code ByteString} then
443     * it will be converted using the {@link ByteString#valueOf(Object)} method.
444     *
445     * @param attributeType
446     *            The attribute type.
447     * @param attributeValue
448     *            The attribute value.
449     * @return The child DN.
450     * @throws UnknownSchemaElementException
451     *             If {@code attributeType} was not found in the default schema.
452     * @throws NullPointerException
453     *             If {@code attributeType} or {@code attributeValue} was
454     *             {@code null}.
455     */
456    public DN child(final String attributeType, final Object attributeValue) {
457        return child(new RDN(attributeType, attributeValue));
458    }
459
460    /** {@inheritDoc} */
461    @Override
462    public int compareTo(final DN dn) {
463        return compareTo(this, dn);
464    }
465
466    /** {@inheritDoc} */
467    @Override
468    public boolean equals(final Object obj) {
469        if (this == obj) {
470            return true;
471        }
472        if (obj instanceof DN) {
473            DN otherDN = (DN) obj;
474            return toNormalizedByteString().equals(otherDN.toNormalizedByteString());
475        }
476        return false;
477    }
478
479    /** {@inheritDoc} */
480    @Override
481    public int hashCode() {
482        return toNormalizedByteString().hashCode();
483    }
484
485    /**
486     * Returns {@code true} if this DN is an immediate child of the provided DN.
487     *
488     * @param dn
489     *            The potential parent DN.
490     * @return {@code true} if this DN is the immediate child of the provided
491     *         DN, otherwise {@code false}.
492     * @throws NullPointerException
493     *             If {@code dn} was {@code null}.
494     */
495    public boolean isChildOf(final DN dn) {
496        // If this is the Root DN then parent will be null but this is ok.
497        return dn.equals(parent);
498    }
499
500    /**
501     * Returns {@code true} if this DN is an immediate child of the provided DN
502     * decoded using the default schema.
503     *
504     * @param dn
505     *            The potential parent DN.
506     * @return {@code true} if this DN is the immediate child of the provided
507     *         DN, otherwise {@code false}.
508     * @throws LocalizedIllegalArgumentException
509     *             If {@code dn} is not a valid LDAP string representation of a
510     *             DN.
511     * @throws NullPointerException
512     *             If {@code dn} was {@code null}.
513     */
514    public boolean isChildOf(final String dn) {
515        // If this is the Root DN then parent will be null but this is ok.
516        return isChildOf(valueOf(dn));
517    }
518
519    /**
520     * Returns {@code true} if this DN matches the provided base DN and search
521     * scope.
522     *
523     * @param dn
524     *            The base DN.
525     * @param scope
526     *            The search scope.
527     * @return {@code true} if this DN matches the provided base DN and search
528     *         scope, otherwise {@code false}.
529     * @throws NullPointerException
530     *             If {@code dn} or {@code scope} was {@code null}.
531     */
532    public boolean isInScopeOf(DN dn, SearchScope scope) {
533        if (scope == SearchScope.BASE_OBJECT) {
534            // The base DN must equal this DN.
535            return equals(dn);
536        } else if (scope == SearchScope.SINGLE_LEVEL) {
537            // The parent DN must equal the base DN.
538            return isChildOf(dn);
539        } else if (scope == SearchScope.SUBORDINATES) {
540            // This DN must be a descendant of the provided base DN, but
541            // not equal to it.
542            return isSubordinateOrEqualTo(dn) && !equals(dn);
543        } else if (scope == SearchScope.WHOLE_SUBTREE) {
544            // This DN must be a descendant of the provided base DN.
545            return isSubordinateOrEqualTo(dn);
546        } else {
547            // This is a scope that we don't recognize.
548            return false;
549        }
550    }
551
552    /**
553     * Returns {@code true} if this DN matches the provided base DN and search
554     * scope.
555     *
556     * @param dn
557     *            The base DN.
558     * @param scope
559     *            The search scope.
560     * @return {@code true} if this DN matches the provided base DN and search
561     *         scope, otherwise {@code false}.
562     * @throws LocalizedIllegalArgumentException
563     *             If {@code dn} is not a valid LDAP string representation of a
564     *             DN.
565     * @throws NullPointerException
566     *             If {@code dn} or {@code scope} was {@code null}.
567     */
568    public boolean isInScopeOf(String dn, SearchScope scope) {
569        return isInScopeOf(valueOf(dn), scope);
570    }
571
572    /**
573     * Returns {@code true} if this DN is the immediate parent of the provided
574     * DN.
575     *
576     * @param dn
577     *            The potential child DN.
578     * @return {@code true} if this DN is the immediate parent of the provided
579     *         DN, otherwise {@code false}.
580     * @throws NullPointerException
581     *             If {@code dn} was {@code null}.
582     */
583    public boolean isParentOf(final DN dn) {
584        // If dn is the Root DN then parent will be null but this is ok.
585        return equals(dn.parent);
586    }
587
588    /**
589     * Returns {@code true} if this DN is the immediate parent of the provided
590     * DN.
591     *
592     * @param dn
593     *            The potential child DN.
594     * @return {@code true} if this DN is the immediate parent of the provided
595     *         DN, otherwise {@code false}.
596     * @throws LocalizedIllegalArgumentException
597     *             If {@code dn} is not a valid LDAP string representation of a
598     *             DN.
599     * @throws NullPointerException
600     *             If {@code dn} was {@code null}.
601     */
602    public boolean isParentOf(final String dn) {
603        // If dn is the Root DN then parent will be null but this is ok.
604        return isParentOf(valueOf(dn));
605    }
606
607    /**
608     * Returns {@code true} if this DN is the Root DN.
609     *
610     * @return {@code true} if this DN is the Root DN, otherwise {@code false}.
611     */
612    public boolean isRootDN() {
613        return size == 0;
614    }
615
616    /**
617     * Returns {@code true} if this DN is subordinate to or equal to the
618     * provided DN.
619     *
620     * @param dn
621     *            The potential child DN.
622     * @return {@code true} if this DN is subordinate to or equal to the
623     *         provided DN, otherwise {@code false}.
624     * @throws NullPointerException
625     *             If {@code dn} was {@code null}.
626     */
627    public boolean isSubordinateOrEqualTo(final DN dn) {
628        if (size < dn.size) {
629            return false;
630        } else if (size == dn.size) {
631            return equals(dn);
632        } else {
633            // dn is a potential superior of this.
634            return parent(size - dn.size).equals(dn);
635        }
636    }
637
638    /**
639     * Returns {@code true} if this DN is subordinate to or equal to the
640     * provided DN.
641     *
642     * @param dn
643     *            The potential child DN.
644     * @return {@code true} if this DN is subordinate to or equal to the
645     *         provided DN, otherwise {@code false}.
646     * @throws LocalizedIllegalArgumentException
647     *             If {@code dn} is not a valid LDAP string representation of a
648     *             DN.
649     * @throws NullPointerException
650     *             If {@code dn} was {@code null}.
651     */
652    public boolean isSubordinateOrEqualTo(final String dn) {
653        return isSubordinateOrEqualTo(valueOf(dn));
654    }
655
656    /**
657     * Returns {@code true} if this DN is superior to or equal to the provided
658     * DN.
659     *
660     * @param dn
661     *            The potential child DN.
662     * @return {@code true} if this DN is superior to or equal to the provided
663     *         DN, otherwise {@code false}.
664     * @throws NullPointerException
665     *             If {@code dn} was {@code null}.
666     */
667    public boolean isSuperiorOrEqualTo(final DN dn) {
668        if (size > dn.size) {
669            return false;
670        } else if (size == dn.size) {
671            return equals(dn);
672        } else {
673            // dn is a potential subordinate of this.
674            return dn.parent(dn.size - size).equals(this);
675        }
676    }
677
678    /**
679     * Returns {@code true} if this DN is superior to or equal to the provided
680     * DN.
681     *
682     * @param dn
683     *            The potential child DN.
684     * @return {@code true} if this DN is superior to or equal to the provided
685     *         DN, otherwise {@code false}.
686     * @throws LocalizedIllegalArgumentException
687     *             If {@code dn} is not a valid LDAP string representation of a
688     *             DN.
689     * @throws NullPointerException
690     *             If {@code dn} was {@code null}.
691     */
692    public boolean isSuperiorOrEqualTo(final String dn) {
693        return isSuperiorOrEqualTo(valueOf(dn));
694    }
695
696    /**
697     * Returns an iterator of the RDNs contained in this DN. The RDNs will be
698     * returned in the order starting with this DN's RDN, followed by the RDN of
699     * the parent DN, and so on.
700     * <p>
701     * Attempts to remove RDNs using an iterator's {@code remove()} method are
702     * not permitted and will result in an {@code UnsupportedOperationException}
703     * being thrown.
704     *
705     * @return An iterator of the RDNs contained in this DN.
706     */
707    @Override
708    public Iterator<RDN> iterator() {
709        return new Iterator<RDN>() {
710            private DN dn = DN.this;
711
712            @Override
713            public boolean hasNext() {
714                return dn.rdn != null;
715            }
716
717            @Override
718            public RDN next() {
719                if (dn.rdn == null) {
720                    throw new NoSuchElementException();
721                }
722
723                final RDN rdn = dn.rdn;
724                dn = dn.parent;
725                return rdn;
726            }
727
728            @Override
729            public void remove() {
730                throw new UnsupportedOperationException();
731            }
732        };
733    }
734
735    /**
736     * Returns the DN whose content is the specified number of RDNs from this
737     * DN. The following equivalences hold:
738     *
739     * <pre>
740     * dn.localName(0).isRootDN();
741     * dn.localName(1).equals(rootDN.child(dn.rdn()));
742     * dn.localName(dn.size()).equals(dn);
743     * </pre>
744     *
745     * @param index
746     *            The number of RDNs to be included in the local name.
747     * @return The DN whose content is the specified number of RDNs from this
748     *         DN.
749     * @throws IllegalArgumentException
750     *             If {@code index} is less than zero.
751     */
752    public DN localName(final int index) {
753        Reject.ifFalse(index >= 0, "index less than zero");
754
755        if (index == 0) {
756            return ROOT_DN;
757        } else if (index >= size) {
758            return this;
759        } else {
760            final DN localName = new DN(this.schema, null, rdn, null, index);
761            DN nextLocalName = localName;
762            DN lastDN = parent;
763            for (int i = index - 1; i > 0; i--) {
764                nextLocalName.parent = new DN(this.schema, null, lastDN.rdn, null, i);
765                nextLocalName = nextLocalName.parent;
766                lastDN = lastDN.parent;
767            }
768            nextLocalName.parent = ROOT_DN;
769            return localName;
770        }
771    }
772
773    /**
774     * Returns the DN which is the immediate parent of this DN, or {@code null}
775     * if this DN is the Root DN.
776     * <p>
777     * This method is equivalent to:
778     *
779     * <pre>
780     * parent(1);
781     * </pre>
782     *
783     * @return The DN which is the immediate parent of this DN, or {@code null}
784     *         if this DN is the Root DN.
785     */
786    public DN parent() {
787        return parent;
788    }
789
790    /**
791     * Returns the DN which is equal to this DN with the specified number of
792     * RDNs removed. Note that if {@code index} is zero then this DN will be
793     * returned (identity).
794     *
795     * @param index
796     *            The number of RDNs to be removed.
797     * @return The DN which is equal to this DN with the specified number of
798     *         RDNs removed, or {@code null} if the parent of the Root DN is
799     *         reached.
800     * @throws IllegalArgumentException
801     *             If {@code index} is less than zero.
802     */
803    public DN parent(final int index) {
804        // We allow size + 1 so that we can return null as the parent of the
805        // Root DN.
806        Reject.ifFalse(index >= 0, "index less than zero");
807
808        DN parentDN = this;
809        for (int i = 0; parentDN != null && i < index; i++) {
810            parentDN = parentDN.parent;
811        }
812        return parentDN;
813    }
814
815    /**
816     * Returns the RDN of this DN, or {@code null} if this DN is the Root DN.
817     *
818     * @return The RDN of this DN, or {@code null} if this DN is the Root DN.
819     */
820    public RDN rdn() {
821        return rdn;
822    }
823
824    /**
825     * Returns a copy of this DN whose parent DN, {@code fromDN}, has been
826     * renamed to the new parent DN, {@code toDN}. If this DN is not subordinate
827     * or equal to {@code fromDN} then this DN is returned (i.e. the DN is not
828     * renamed).
829     *
830     * @param fromDN
831     *            The old parent DN.
832     * @param toDN
833     *            The new parent DN.
834     * @return The renamed DN, or this DN if no renaming was performed.
835     * @throws NullPointerException
836     *             If {@code fromDN} or {@code toDN} was {@code null}.
837     */
838    public DN rename(final DN fromDN, final DN toDN) {
839        Reject.ifNull(fromDN, toDN);
840
841        if (!isSubordinateOrEqualTo(fromDN)) {
842            return this;
843        } else if (equals(fromDN)) {
844            return toDN;
845        } else {
846            return toDN.child(localName(size - fromDN.size));
847        }
848    }
849
850    /**
851     * Returns the number of RDN components in this DN.
852     *
853     * @return The number of RDN components in this DN.
854     */
855    public int size() {
856        return size;
857    }
858
859    /**
860     * Returns the RFC 4514 string representation of this DN.
861     *
862     * @return The RFC 4514 string representation of this DN.
863     * @see <a href="http://tools.ietf.org/html/rfc4514">RFC 4514 - Lightweight
864     *      Directory Access Protocol (LDAP): String Representation of
865     *      Distinguished Names </a>
866     */
867    @Override
868    public String toString() {
869        // We don't care about potential race conditions here.
870        if (stringValue == null) {
871            final StringBuilder builder = new StringBuilder();
872            rdn.toString(builder);
873            if (!parent.isRootDN()) {
874                builder.append(',');
875                builder.append(parent);
876            }
877            stringValue = builder.toString();
878        }
879        return stringValue;
880    }
881
882    /**
883     * Retrieves a normalized byte string representation of this DN.
884     * <p>
885     * This representation is suitable for equality and comparisons, and
886     * for providing a natural hierarchical ordering.
887     * However, it is not a valid DN and can't be reverted to a valid DN.
888     * You should consider using a {@code CompactDn} as an alternative.
889     *
890     * @return The normalized string representation of this DN.
891     */
892    public ByteString toNormalizedByteString() {
893        if (normalizedDN == null) {
894            if (rdn() == null) {
895                normalizedDN = ByteString.empty();
896            } else {
897                final ByteStringBuilder builder = new ByteStringBuilder();
898                int i = size() - 1;
899                parent(i).rdn().toNormalizedByteString(builder);
900                for (i--; i >= 0; i--) {
901                    final RDN rdn = parent(i).rdn();
902                    // Only add a separator if the RDN is not RDN.maxValue().
903                    if (rdn.size() != 0) {
904                        builder.append(DN.NORMALIZED_RDN_SEPARATOR);
905                    }
906                    rdn.toNormalizedByteString(builder);
907                }
908                normalizedDN = builder.toByteString();
909            }
910        }
911        return normalizedDN;
912    }
913
914    /**
915     * Retrieves a normalized string representation of this DN.
916     * <p>
917     * This representation is safe to use in an URL or in a file name.
918     * However, it is not a valid DN and can't be reverted to a valid DN.
919     *
920     * @return The normalized string representation of this DN.
921     */
922    public String toNormalizedUrlSafeString() {
923        if (rdn() == null) {
924            return "";
925        }
926
927        final StringBuilder builder = new StringBuilder();
928        int i = size() - 1;
929        parent(i).rdn().toNormalizedUrlSafeString(builder);
930        for (i--; i >= 0; i--) {
931            final RDN rdn = parent(i).rdn();
932            // Only add a separator if the RDN is not RDN.maxValue().
933            if (rdn.size() != 0) {
934                builder.append(',');
935            }
936            rdn.toNormalizedUrlSafeString(builder);
937        }
938        return builder.toString();
939    }
940
941    /**
942     * A compact representation of a DN, suitable for equality and comparisons, and providing a natural hierarchical
943     * ordering.
944     * <p>
945     * This representation should be used when it is important to reduce memory usage. The memory consumption compared
946     * to a regular DN object is minimal. Prototypical usage is for static groups implementation where large groups of
947     * DNs must be recorded and must be converted back to DNs.
948     * <p>
949     * This representation can be created either eagerly or lazily.
950     * <ul>
951     *   <li>eagerly: the normalized value is computed immediately at creation time.</li>
952     *   <li>lazily: the normalized value is computed only the first time it is needed.</li>
953     * </ul>
954     *
955     * @Deprecated This class will eventually be replaced by a compact implementation of a DN.
956     */
957    public static final class CompactDn implements Comparable<CompactDn> {
958
959        /** Original string corresponding to the DN. */
960        private final byte[] originalValue;
961
962        /**
963         * Normalized byte string, suitable for equality and comparisons, and providing a natural hierarchical ordering,
964         * but not usable as a valid DN.
965         */
966        private volatile byte[] normalizedValue;
967
968        private final Schema schema;
969
970        private CompactDn(final DN dn) {
971            this.originalValue = dn.stringValue != null ? getBytes(dn.stringValue) : new byte[0];
972            this.schema = dn.schema;
973        }
974
975        /** {@inheritDoc} */
976        @Override
977        public int compareTo(final CompactDn other) {
978            byte[] normValue = getNormalizedValue();
979            byte[] otherNormValue = other.getNormalizedValue();
980            return ByteString.compareTo(normValue, 0, normValue.length, otherNormValue, 0, otherNormValue.length);
981        }
982
983        /**
984         * Returns the DN corresponding to this compact representation.
985         *
986         *  @return the DN
987         */
988        public DN toDn() {
989            return DN.valueOf(ByteString.toString(originalValue, 0, originalValue.length), schema);
990        }
991
992        /** {@inheritDoc} */
993        @Override
994        public int hashCode() {
995            return Arrays.hashCode(getNormalizedValue());
996        }
997
998        /** {@inheritDoc} */
999        @Override
1000        public boolean equals(Object obj) {
1001            if (this == obj) {
1002                return true;
1003            } else if (obj instanceof CompactDn) {
1004                final CompactDn other = (CompactDn) obj;
1005                return Arrays.equals(getNormalizedValue(), other.getNormalizedValue());
1006            } else {
1007                return false;
1008            }
1009        }
1010
1011        /** {@inheritDoc} */
1012        @Override
1013        public String toString() {
1014            return ByteString.toString(originalValue, 0, originalValue.length);
1015        }
1016
1017        private byte[] getNormalizedValue() {
1018            if (normalizedValue == null) {
1019                normalizedValue = toDn().toNormalizedByteString().toByteArray();
1020            }
1021            return normalizedValue;
1022        }
1023    }
1024
1025    /**
1026     * Returns a compact representation of this DN, with lazy evaluation of the normalized value.
1027     *
1028     * @return the DN compact representation
1029     */
1030    public CompactDn compact() {
1031        return new CompactDn(this);
1032    }
1033
1034}