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 static com.forgerock.opendj.ldap.CoreMessages.ERR_RDN_DUPLICATE_AVA_TYPES;
020import static com.forgerock.opendj.ldap.CoreMessages.ERR_RDN_NO_AVAS;
021import static com.forgerock.opendj.ldap.CoreMessages.ERR_RDN_TRAILING_GARBAGE;
022import static com.forgerock.opendj.ldap.CoreMessages.ERR_RDN_TYPE_NOT_FOUND;
023import static org.forgerock.opendj.ldap.DN.AVA_CHAR_SEPARATOR;
024import static org.forgerock.opendj.ldap.DN.NORMALIZED_AVA_SEPARATOR;
025import static org.forgerock.opendj.ldap.DN.NORMALIZED_RDN_SEPARATOR;
026import static org.forgerock.opendj.ldap.DN.RDN_CHAR_SEPARATOR;
027
028import java.util.ArrayList;
029import java.util.Arrays;
030import java.util.Collection;
031import java.util.Collections;
032import java.util.Iterator;
033import java.util.List;
034import java.util.TreeSet;
035
036import org.forgerock.i18n.LocalizedIllegalArgumentException;
037import org.forgerock.opendj.ldap.schema.AttributeType;
038import org.forgerock.opendj.ldap.schema.Schema;
039import org.forgerock.opendj.ldap.schema.UnknownSchemaElementException;
040import org.forgerock.util.Reject;
041
042import com.forgerock.opendj.util.Iterators;
043import com.forgerock.opendj.util.SubstringReader;
044
045/**
046 * A relative distinguished name (RDN) as defined in RFC 4512 section 2.3 is the
047 * name of an entry relative to its immediate superior. An RDN is composed of an
048 * unordered set of one or more attribute value assertions (AVA) consisting of
049 * an attribute description with zero options and an attribute value. These AVAs
050 * are chosen to match attribute values (each a distinguished value) of the
051 * entry.
052 * <p>
053 * An entry's relative distinguished name must be unique among all immediate
054 * subordinates of the entry's immediate superior (i.e. all siblings).
055 * <p>
056 * The following are examples of string representations of RDNs:
057 *
058 * <pre>
059 * uid=12345
060 * ou=Engineering
061 * cn=Kurt Zeilenga+L=Redwood Shores
062 * </pre>
063 *
064 * The last is an example of a multi-valued RDN; that is, an RDN composed of
065 * multiple AVAs.
066 *
067 * @see <a href="http://tools.ietf.org/html/rfc4512#section-2.3">RFC 4512 -
068 *      Lightweight Directory Access Protocol (LDAP): Directory Information
069 *      Models </a>
070 */
071public final class RDN implements Iterable<AVA>, Comparable<RDN> {
072
073    /**
074     * A constant holding a special RDN having zero AVAs
075     * and which sorts before any RDN other than itself.
076     */
077    private static final RDN MIN_VALUE = new RDN();
078    /**
079     * A constant holding a special RDN having zero AVAs
080     * and which sorts after any RDN other than itself.
081     */
082    private static final RDN MAX_VALUE = new RDN();
083
084    /**
085     * Returns a constant containing a special RDN which sorts before any
086     * RDN other than itself. This RDN may be used in order to perform
087     * range queries on DN keyed collections such as {@code SortedSet}s and
088     * {@code SortedMap}s. For example, the following code can be used to
089     * construct a range whose contents is a sub-tree of entries, excluding the base entry:
090     *
091     * <pre>
092     * SortedMap<DN, Entry> entries = ...;
093     * DN baseDN = ...;
094     *
095     * // Returns a map containing the baseDN and all of its subordinates.
096     * SortedMap<DN,Entry> subtree = entries.subMap(
097     *     baseDN.child(RDN.minValue()), baseDN.child(RDN.maxValue()));
098     * </pre>
099     *
100     * @return A constant containing a special RDN which sorts before any
101     *         RDN other than itself.
102     * @see #maxValue()
103     */
104    public static RDN minValue() {
105        return MIN_VALUE;
106    }
107
108    /**
109     * Returns a constant containing a special RDN which sorts after any
110     * RDN other than itself. This RDN may be used in order to perform
111     * range queries on DN keyed collections such as {@code SortedSet}s and
112     * {@code SortedMap}s. For example, the following code can be used to
113     * construct a range whose contents is a sub-tree of entries:
114     *
115     * <pre>
116     * SortedMap<DN, Entry> entries = ...;
117     * DN baseDN = ...;
118     *
119     * // Returns a map containing the baseDN and all of its subordinates.
120     * SortedMap<DN,Entry> subtree = entries.subMap(baseDN, baseDN.child(RDN.maxValue()));
121     * </pre>
122     *
123     * @return A constant containing a special RDN which sorts after any
124     *         RDN other than itself.
125     * @see #minValue()
126     */
127    public static RDN maxValue() {
128        return MAX_VALUE;
129    }
130
131    /**
132     * Parses the provided LDAP string representation of an RDN using the
133     * default schema.
134     *
135     * @param rdn
136     *            The LDAP string representation of a RDN.
137     * @return The parsed RDN.
138     * @throws LocalizedIllegalArgumentException
139     *             If {@code rdn} is not a valid LDAP string representation of a
140     *             RDN.
141     * @throws NullPointerException
142     *             If {@code rdn} was {@code null}.
143     */
144    public static RDN valueOf(final String rdn) {
145        return valueOf(rdn, Schema.getDefaultSchema());
146    }
147
148    /**
149     * Parses the provided LDAP string representation of a RDN using the
150     * provided schema.
151     *
152     * @param rdn
153     *            The LDAP string representation of a RDN.
154     * @param schema
155     *            The schema to use when parsing the RDN.
156     * @return The parsed RDN.
157     * @throws LocalizedIllegalArgumentException
158     *             If {@code rdn} is not a valid LDAP string representation of a
159     *             RDN.
160     * @throws NullPointerException
161     *             If {@code rdn} or {@code schema} was {@code null}.
162     */
163    public static RDN valueOf(final String rdn, final Schema schema) {
164        final SubstringReader reader = new SubstringReader(rdn);
165        final RDN parsedRdn;
166        try {
167            parsedRdn = decode(reader, schema);
168        } catch (final UnknownSchemaElementException e) {
169            throw new LocalizedIllegalArgumentException(ERR_RDN_TYPE_NOT_FOUND.get(rdn, e.getMessageObject()));
170        }
171        if (reader.remaining() > 0) {
172            throw new LocalizedIllegalArgumentException(
173                    ERR_RDN_TRAILING_GARBAGE.get(rdn, reader.read(reader.remaining())));
174        }
175        return parsedRdn;
176    }
177
178    static RDN decode(final SubstringReader reader, final Schema schema) {
179        final AVA firstAVA = AVA.decode(reader, schema);
180
181        // Skip over any spaces that might be after the attribute value.
182        reader.skipWhitespaces();
183
184        reader.mark();
185        if (reader.remaining() > 0 && reader.read() == '+') {
186            final List<AVA> avas = new ArrayList<>();
187            avas.add(firstAVA);
188
189            do {
190                avas.add(AVA.decode(reader, schema));
191
192                // Skip over any spaces that might be after the attribute value.
193                reader.skipWhitespaces();
194
195                reader.mark();
196            } while (reader.remaining() > 0 && reader.read() == '+');
197
198            reader.reset();
199            return new RDN(avas);
200        } else {
201            reader.reset();
202            return new RDN(firstAVA);
203        }
204    }
205
206    /** In original order. */
207    private final AVA[] avas;
208
209    /**
210     * We need to store the original string value if provided in order to
211     * preserve the original whitespace.
212     */
213    private String stringValue;
214
215    /**
216     * Creates a new RDN using the provided attribute type and value.
217     * <p>
218     * If {@code attributeValue} is not an instance of {@code ByteString} then
219     * it will be converted using the {@link ByteString#valueOfObject(Object)} method.
220     *
221     * @param attributeType
222     *            The attribute type.
223     * @param attributeValue
224     *            The attribute value.
225     * @throws NullPointerException
226     *             If {@code attributeType} or {@code attributeValue} was
227     *             {@code null}.
228     */
229    public RDN(final AttributeType attributeType, final Object attributeValue) {
230        this.avas = new AVA[] { new AVA(attributeType, attributeValue) };
231    }
232
233    /**
234     * Creates a new RDN using the provided attribute type and value decoded
235     * using the default schema.
236     * <p>
237     * If {@code attributeValue} is not an instance of {@code ByteString} then
238     * it will be converted using the {@link ByteString#valueOfObject(Object)} method.
239     *
240     * @param attributeType
241     *            The attribute type.
242     * @param attributeValue
243     *            The attribute value.
244     * @throws UnknownSchemaElementException
245     *             If {@code attributeType} was not found in the default schema.
246     * @throws NullPointerException
247     *             If {@code attributeType} or {@code attributeValue} was
248     *             {@code null}.
249     */
250    public RDN(final String attributeType, final Object attributeValue) {
251        this.avas = new AVA[] { new AVA(attributeType, attributeValue) };
252    }
253
254    /**
255     * Creates a new RDN using the provided AVAs.
256     *
257     * @param avas
258     *            The attribute-value assertions used to build this RDN.
259     * @throws NullPointerException
260     *             If {@code avas} is {@code null} or contains a null ava.
261     * @throws IllegalArgumentException
262     *             If {@code avas} is empty.
263     */
264    public RDN(final AVA... avas) {
265        Reject.ifNull(avas);
266        this.avas = validateAvas(avas);
267    }
268
269    private AVA[] validateAvas(final AVA[] avas) {
270        switch (avas.length) {
271        case 0:
272            throw new LocalizedIllegalArgumentException(ERR_RDN_NO_AVAS.get());
273        case 1:
274            // Guaranteed to be valid.
275            break;
276        case 2:
277            if (avas[0].getAttributeType().equals(avas[1].getAttributeType())) {
278                throw new LocalizedIllegalArgumentException(
279                        ERR_RDN_DUPLICATE_AVA_TYPES.get(avas[0].getAttributeName()));
280            }
281            break;
282        default:
283            final AVA[] sortedAVAs = Arrays.copyOf(avas, avas.length);
284            Arrays.sort(sortedAVAs);
285            AttributeType previousAttributeType = null;
286            for (AVA ava : sortedAVAs) {
287                if (ava.getAttributeType().equals(previousAttributeType)) {
288                    throw new LocalizedIllegalArgumentException(
289                            ERR_RDN_DUPLICATE_AVA_TYPES.get(ava.getAttributeName()));
290                }
291                previousAttributeType = ava.getAttributeType();
292            }
293        }
294        return avas;
295    }
296
297    /**
298     * Creates a new RDN using the provided AVAs.
299     *
300     * @param avas
301     *            The attribute-value assertions used to build this RDN.
302     * @throws NullPointerException
303     *             If {@code ava} is {@code null} or contains null ava.
304     * @throws IllegalArgumentException
305     *             If {@code avas} is empty.
306     */
307    public RDN(Collection<AVA> avas) {
308        Reject.ifNull(avas);
309        this.avas = validateAvas(avas.toArray(new AVA[avas.size()]));
310    }
311
312    // Special constructor for min/max RDN values.
313    private RDN() {
314        this.avas = new AVA[0];
315        this.stringValue = "";
316    }
317
318    @Override
319    public int compareTo(final RDN rdn) {
320        // FIXME how about replacing this method body with the following code?
321        // return toNormalizedByteString().compareTo(rdn.toNormalizedByteString())
322
323        // Identity.
324        if (this == rdn) {
325            return 0;
326        }
327
328        // MAX_VALUE is always greater than any other RDN other than itself.
329        if (this == MAX_VALUE) {
330            return 1;
331        }
332        if (rdn == MAX_VALUE) {
333            return -1;
334        }
335
336        // MIN_VALUE is always less than any other RDN other than itself.
337        if (this == MIN_VALUE) {
338            return -1;
339        }
340        if (rdn == MIN_VALUE) {
341            return 1;
342        }
343
344        // Compare number of AVAs first as this is quick and easy.
345        final int sz1 = avas.length;
346        final int sz2 = rdn.avas.length;
347        if (sz1 != sz2) {
348            return sz1 - sz2 > 0 ? 1 : -1;
349        }
350
351        // Fast path for common case.
352        if (sz1 == 1) {
353            return avas[0].compareTo(rdn.avas[0]);
354        }
355
356        // Need to sort the AVAs before comparing.
357        final AVA[] a1 = new AVA[sz1];
358        System.arraycopy(avas, 0, a1, 0, sz1);
359        Arrays.sort(a1);
360
361        final AVA[] a2 = new AVA[sz1];
362        System.arraycopy(rdn.avas, 0, a2, 0, sz1);
363        Arrays.sort(a2);
364
365        for (int i = 0; i < sz1; i++) {
366            final int result = a1[i].compareTo(a2[i]);
367            if (result != 0) {
368                return result;
369            }
370        }
371
372        return 0;
373    }
374
375    @Override
376    public boolean equals(final Object obj) {
377        if (this == obj) {
378            return true;
379        } else if (obj instanceof RDN) {
380            return compareTo((RDN) obj) == 0;
381        } else {
382            return false;
383        }
384    }
385
386    /**
387     * Returns the attribute value contained in this RDN which is associated
388     * with the provided attribute type, or {@code null} if this RDN does not
389     * include such an attribute value.
390     *
391     * @param attributeType
392     *            The attribute type.
393     * @return The attribute value.
394     */
395    public ByteString getAttributeValue(final AttributeType attributeType) {
396        for (final AVA ava : avas) {
397            if (ava.getAttributeType().equals(attributeType)) {
398                return ava.getAttributeValue();
399            }
400        }
401        return null;
402    }
403
404    /**
405     * Returns the first AVA contained in this RDN.
406     *
407     * @return The first AVA contained in this RDN.
408     */
409    public AVA getFirstAVA() {
410        return avas[0];
411    }
412
413    @Override
414    public int hashCode() {
415        // Avoid an algorithm that requires the AVAs to be sorted.
416        int hash = 0;
417        for (final AVA ava : avas) {
418            hash += ava.hashCode();
419        }
420        return hash;
421    }
422
423    /**
424     * Returns {@code true} if this RDN contains more than one AVA.
425     *
426     * @return {@code true} if this RDN contains more than one AVA, otherwise
427     *         {@code false}.
428     */
429    public boolean isMultiValued() {
430        return avas.length > 1;
431    }
432
433    /**
434     * Indicates whether this RDN includes the specified attribute type.
435     *
436     * @param attributeType  The attribute type for which to make the determination.
437     * @return {@code true} if the RDN includes the specified attribute type,
438     *         or {@code false} if not.
439     */
440    public boolean hasAttributeType(AttributeType attributeType) {
441        for (AVA ava : avas) {
442            if (ava.getAttributeType().equals(attributeType)) {
443                return true;
444            }
445        }
446        return false;
447    }
448
449    /**
450     * Returns an iterator of the AVAs contained in this RDN. The AVAs will be
451     * returned in the user provided order.
452     * <p>
453     * Attempts to remove AVAs using an iterator's {@code remove()} method are
454     * not permitted and will result in an {@code UnsupportedOperationException}
455     * being thrown.
456     *
457     * @return An iterator of the AVAs contained in this RDN.
458     */
459    @Override
460    public Iterator<AVA> iterator() {
461        return Iterators.arrayIterator(avas);
462    }
463
464    /**
465     * Returns the number of AVAs in this RDN.
466     *
467     * @return The number of AVAs in this RDN.
468     */
469    public int size() {
470        return avas.length;
471    }
472
473    /**
474     * Returns the RFC 4514 string representation of this RDN.
475     *
476     * @return The RFC 4514 string representation of this RDN.
477     * @see <a href="http://tools.ietf.org/html/rfc4514">RFC 4514 - Lightweight
478     *      Directory Access Protocol (LDAP): String Representation of
479     *      Distinguished Names </a>
480     */
481    @Override
482    public String toString() {
483        // We don't care about potential race conditions here.
484        if (stringValue == null) {
485            final StringBuilder builder = new StringBuilder();
486            avas[0].toString(builder);
487            for (int i = 1; i < avas.length; i++) {
488                builder.append(AVA_CHAR_SEPARATOR);
489                avas[i].toString(builder);
490            }
491            stringValue = builder.toString();
492        }
493        return stringValue;
494    }
495
496    /**
497     * Returns the normalized byte string representation of this RDN.
498     * <p>
499     * The representation is not a valid RDN.
500     *
501     * @param builder
502     *            The builder to use to construct the normalized byte string.
503     * @return The normalized byte string representation.
504     * @see DN#toNormalizedByteString()
505     */
506    ByteStringBuilder toNormalizedByteString(final ByteStringBuilder builder) {
507        switch (size()) {
508        case 0:
509            if (this == MIN_VALUE) {
510                builder.appendByte(NORMALIZED_RDN_SEPARATOR);
511            } else { // can only be MAX_VALUE
512                builder.appendByte(NORMALIZED_AVA_SEPARATOR);
513            }
514            break;
515        case 1:
516            builder.appendByte(NORMALIZED_RDN_SEPARATOR);
517            getFirstAVA().toNormalizedByteString(builder);
518            break;
519        default:
520            builder.appendByte(NORMALIZED_RDN_SEPARATOR);
521            Iterator<AVA> it = getSortedAvas();
522            it.next().toNormalizedByteString(builder);
523            while (it.hasNext()) {
524                builder.appendByte(NORMALIZED_AVA_SEPARATOR);
525                it.next().toNormalizedByteString(builder);
526            }
527            break;
528        }
529        return builder;
530    }
531
532    /**
533     * Retrieves a normalized string representation of this RDN.
534     * <p>
535     * This representation is safe to use in an URL or in a file name.
536     * However, it is not a valid RDN and can't be reverted to a valid RDN.
537     *
538     * @return The normalized string representation of this RDN.
539     * @see DN#toNormalizedUrlSafeString()
540     */
541    StringBuilder toNormalizedUrlSafeString(final StringBuilder builder) {
542        switch (size()) {
543        case 0:
544            // since MIN_VALUE and MAX_VALUE are only used for sorting DNs,
545            // it is strange to call toNormalizedUrlSafeString() on one of them
546            if (this == MIN_VALUE) {
547                builder.append(RDN_CHAR_SEPARATOR);
548            } else { // can only be MAX_VALUE
549                builder.append(AVA_CHAR_SEPARATOR);
550            }
551            break;
552        case 1:
553            getFirstAVA().toNormalizedUrlSafe(builder);
554            break;
555        default:
556            Iterator<AVA> it = getSortedAvas();
557            it.next().toNormalizedUrlSafe(builder);
558            while (it.hasNext()) {
559                builder.append(AVA_CHAR_SEPARATOR);
560                it.next().toNormalizedUrlSafe(builder);
561            }
562            break;
563        }
564        return builder;
565    }
566
567    private Iterator<AVA> getSortedAvas() {
568        TreeSet<AVA> sortedAvas = new TreeSet<>();
569        Collections.addAll(sortedAvas, avas);
570        return sortedAvas.iterator();
571    }
572}