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