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 2010 Sun Microsystems, Inc.
025 *      Portions copyright 2012-2015 ForgeRock AS.
026 */
027package org.forgerock.opendj.ldap;
028
029import static com.forgerock.opendj.ldap.CoreMessages.*;
030
031import java.util.ArrayList;
032import java.util.Arrays;
033import java.util.Collection;
034import java.util.Comparator;
035import java.util.LinkedList;
036import java.util.List;
037import java.util.StringTokenizer;
038
039import org.forgerock.i18n.LocalizableMessage;
040import org.forgerock.i18n.LocalizedIllegalArgumentException;
041import org.forgerock.opendj.ldap.schema.MatchingRule;
042import org.forgerock.opendj.ldap.schema.Schema;
043import org.forgerock.util.Reject;
044
045/**
046 * A search result sort key as defined in RFC 2891 is used to specify how search
047 * result entries should be ordered. Sort keys are used with the server side
048 * sort request control
049 * {@link org.forgerock.opendj.ldap.controls.ServerSideSortRequestControl}, but
050 * could also be used for performing client side sorting as well.
051 * <p>
052 * The following example illustrates how a single sort key may be used to sort
053 * entries as they are returned from a search operation using the {@code cn}
054 * attribute as the sort key:
055 *
056 * <pre>
057 * Connection connection = ...;
058 * SearchRequest request = ...;
059 *
060 * Comparator&lt;Entry> comparator = SortKey.comparator("cn");
061 * Set&lt;SearchResultEntry>; results = new TreeSet&lt;SearchResultEntry>(comparator);
062 *
063 * connection.search(request, results);
064 * </pre>
065 *
066 * A sort key includes an attribute description and a boolean value that
067 * indicates whether the sort should be ascending or descending. It may also
068 * contain a specific ordering matching rule that should be used for the sorting
069 * process, although if none is provided it will use the default ordering
070 * matching rule for the attribute type.
071 *
072 * @see <a href="http://tools.ietf.org/html/rfc2891">RFC 2891 - LDAP Control
073 *      Extension for Server Side Sorting of Search Results </a>
074 */
075public final class SortKey {
076    private static final class CompositeEntryComparator implements Comparator<Entry> {
077        private final List<Comparator<Entry>> comparators;
078
079        private CompositeEntryComparator(final List<Comparator<Entry>> comparators) {
080            this.comparators = comparators;
081        }
082
083        public int compare(final Entry entry1, final Entry entry2) {
084            for (final Comparator<Entry> comparator : comparators) {
085                final int result = comparator.compare(entry1, entry2);
086                if (result != 0) {
087                    return result;
088                }
089            }
090            return 0;
091        }
092
093    }
094
095    /**
096     * A comparator which can be used to compare entries using a sort key.
097     */
098    private static final class EntryComparator implements Comparator<Entry> {
099        private final AttributeDescription attributeDescription;
100        private final MatchingRule matchingRule;
101        private final boolean isReverseOrder;
102
103        private EntryComparator(final AttributeDescription attributeDescription,
104                final MatchingRule matchingRule, final boolean isReverseOrder) {
105            this.attributeDescription = attributeDescription;
106            this.matchingRule = matchingRule;
107            this.isReverseOrder = isReverseOrder;
108        }
109
110        /**
111         * We must use the lowest available value in both entries and missing
112         * attributes sort last.
113         */
114        public int compare(final Entry entry1, final Entry entry2) {
115            // Find and normalize the lowest value attribute in each entry.
116            final ByteString normalizedValue1 = lowestValueOf(entry1);
117            final ByteString normalizedValue2 = lowestValueOf(entry2);
118
119            // Entries with missing attributes always sort after (regardless of
120            // order).
121            if (normalizedValue1 == null) {
122                return normalizedValue2 != null ? 1 : 0;
123            } else if (normalizedValue2 == null) {
124                return -1;
125            } else if (isReverseOrder) {
126                return normalizedValue2.compareTo(normalizedValue1);
127            } else {
128                return normalizedValue1.compareTo(normalizedValue2);
129            }
130        }
131
132        private ByteString lowestValueOf(final Entry entry) {
133            ByteString normalizedValue = null;
134            for (final Attribute attribute : entry.getAllAttributes(attributeDescription)) {
135                for (final ByteString value : attribute) {
136                    try {
137                        final ByteString tmp = matchingRule.normalizeAttributeValue(value);
138                        if (normalizedValue == null || tmp.compareTo(normalizedValue) < 0) {
139                            normalizedValue = tmp;
140                        }
141                    } catch (final DecodeException ignored) {
142                        // Ignore the error - treat the value as missing.
143                    }
144                }
145            }
146            return normalizedValue;
147        }
148
149    }
150
151    /**
152     * Returns a {@code Comparator} which can be used to compare entries using
153     * the provided list of sort keys. The sort keys will be decoded using the
154     * default schema.
155     *
156     * @param keys
157     *            The list of sort keys.
158     * @return The {@code Comparator}.
159     * @throws LocalizedIllegalArgumentException
160     *             If one of the sort keys could not be converted to a
161     *             comparator.
162     * @throws IllegalArgumentException
163     *             If {@code keys} was empty.
164     * @throws NullPointerException
165     *             If {@code keys} was {@code null}.
166     */
167    public static Comparator<Entry> comparator(final Collection<SortKey> keys) {
168        return comparator(Schema.getDefaultSchema(), keys);
169    }
170
171    /**
172     * Returns a {@code Comparator} which can be used to compare entries using
173     * the provided list of sort keys. The sort keys will be decoded using the
174     * provided schema.
175     *
176     * @param schema
177     *            The schema which should be used for decoding the sort keys.
178     * @param keys
179     *            The list of sort keys.
180     * @return The {@code Comparator}.
181     * @throws LocalizedIllegalArgumentException
182     *             If one of the sort keys could not be converted to a
183     *             comparator.
184     * @throws IllegalArgumentException
185     *             If {@code keys} was empty.
186     * @throws NullPointerException
187     *             If {@code schema} or {@code keys} was {@code null}.
188     */
189    public static Comparator<Entry> comparator(final Schema schema, final Collection<SortKey> keys) {
190        Reject.ifNull(schema, keys);
191        Reject.ifFalse(!keys.isEmpty(), "keys must not be empty");
192
193        final List<Comparator<Entry>> comparators = new ArrayList<>(keys.size());
194        for (final SortKey key : keys) {
195            comparators.add(key.comparator(schema));
196        }
197        return new CompositeEntryComparator(comparators);
198    }
199
200    /**
201     * Returns a {@code Comparator} which can be used to compare entries using
202     * the provided list of sort keys. The sort keys will be decoded using the
203     * provided schema.
204     *
205     * @param schema
206     *            The schema which should be used for decoding the sort keys.
207     * @param keys
208     *            The list of sort keys.
209     * @return The {@code Comparator}.
210     * @throws LocalizedIllegalArgumentException
211     *             If one of the sort keys could not be converted to a
212     *             comparator.
213     * @throws IllegalArgumentException
214     *             If {@code keys} was empty.
215     * @throws NullPointerException
216     *             If {@code schema} or {@code keys} was {@code null}.
217     */
218    public static Comparator<Entry> comparator(final Schema schema, final SortKey... keys) {
219        return comparator(schema, Arrays.asList(keys));
220    }
221
222    /**
223     * Returns a {@code Comparator} which can be used to compare entries using
224     * the provided list of sort keys. The sort keys will be decoded using the
225     * default schema.
226     *
227     * @param keys
228     *            The list of sort keys.
229     * @return The {@code Comparator}.
230     * @throws LocalizedIllegalArgumentException
231     *             If one of the sort keys could not be converted to a
232     *             comparator.
233     * @throws IllegalArgumentException
234     *             If {@code keys} was empty.
235     * @throws NullPointerException
236     *             If {@code keys} was {@code null}.
237     */
238    public static Comparator<Entry> comparator(final SortKey... keys) {
239        return comparator(Schema.getDefaultSchema(), keys);
240    }
241
242    /**
243     * Returns a {@code Comparator} which can be used to compare entries using
244     * the provided string representation of a list of sort keys. The sort keys
245     * will be decoded using the default schema. The string representation is
246     * comprised of a comma separate list of sort keys as defined in
247     * {@link #valueOf(String)}. There must be at least one sort key present in
248     * the string representation.
249     *
250     * @param sortKeys
251     *            The list of sort keys.
252     * @return The {@code Comparator}.
253     * @throws LocalizedIllegalArgumentException
254     *             If {@code sortKeys} is not a valid string representation of a
255     *             list of sort keys, or if one of the sort keys could not be
256     *             converted to a comparator.
257     * @throws NullPointerException
258     *             If {@code sortKeys} was {@code null}.
259     */
260    public static Comparator<Entry> comparator(final String sortKeys) {
261        Reject.ifNull(sortKeys);
262
263        final List<Comparator<Entry>> comparators = new LinkedList<>();
264        final StringTokenizer tokenizer = new StringTokenizer(sortKeys, ",");
265        while (tokenizer.hasMoreTokens()) {
266            final String token = tokenizer.nextToken().trim();
267            comparators.add(valueOf(token).comparator());
268        }
269        if (comparators.isEmpty()) {
270            final LocalizableMessage message = ERR_SORT_KEY_NO_SORT_KEYS.get(sortKeys);
271            throw new LocalizedIllegalArgumentException(message);
272        }
273        return new CompositeEntryComparator(comparators);
274    }
275
276    /**
277     * Parses the provided string representation of a sort key as a
278     * {@code SortKey}. The string representation has the following ABNF (see
279     * RFC 4512 for definitions of the elements below):
280     *
281     * <pre>
282     *   SortKey = [ PLUS / HYPHEN ]    ; order specifier
283     *             attributedescription ; attribute description
284     *             [ COLON oid ]        ; ordering matching rule OID
285     * </pre>
286     *
287     * Examples:
288     *
289     * <pre>
290     *   cn                           ; case ignore ascending sort on "cn"
291     *   -cn                          ; case ignore descending sort on "cn"
292     *   +cn;lang-fr                  ; case ignore ascending sort on "cn;lang-fr"
293     *   -cn;lang-fr:caseExactMatch   ; case exact ascending sort on "cn;lang-fr"
294     * </pre>
295     *
296     * @param sortKey
297     *            The string representation of a sort key.
298     * @return The parsed {@code SortKey}.
299     * @throws LocalizedIllegalArgumentException
300     *             If {@code sortKey} is not a valid string representation of a
301     *             sort key.
302     * @throws NullPointerException
303     *             If {@code sortKey} was {@code null}.
304     */
305    public static SortKey valueOf(String sortKey) {
306        Reject.ifNull(sortKey);
307
308        boolean reverseOrder = false;
309        if (sortKey.startsWith("-")) {
310            reverseOrder = true;
311            sortKey = sortKey.substring(1);
312        } else if (sortKey.startsWith("+")) {
313            sortKey = sortKey.substring(1);
314        }
315
316        final int colonPos = sortKey.indexOf(':');
317        if (colonPos < 0) {
318            if (sortKey.length() == 0) {
319                final LocalizableMessage message = ERR_SORT_KEY_NO_ATTR_NAME.get(sortKey);
320                throw new LocalizedIllegalArgumentException(message);
321            }
322
323            return new SortKey(sortKey, reverseOrder, null);
324        } else if (colonPos == 0) {
325            final LocalizableMessage message = ERR_SORT_KEY_NO_ATTR_NAME.get(sortKey);
326            throw new LocalizedIllegalArgumentException(message);
327        } else if (colonPos == (sortKey.length() - 1)) {
328            final LocalizableMessage message = ERR_SORT_KEY_NO_MATCHING_RULE.get(sortKey);
329            throw new LocalizedIllegalArgumentException(message);
330        } else {
331            final String attrName = sortKey.substring(0, colonPos);
332            final String ruleID = sortKey.substring(colonPos + 1);
333
334            return new SortKey(attrName, reverseOrder, ruleID);
335        }
336    }
337
338    private final String attributeDescription;
339
340    private final String orderingMatchingRule;
341
342    private final boolean isReverseOrder;
343
344    /**
345     * Creates a new sort key using the provided attribute description. The
346     * returned sort key will compare attributes in the order specified using
347     * the named ordering matching rule.
348     *
349     * @param attributeDescription
350     *            The name of the attribute to be sorted using this sort key.
351     * @param isReverseOrder
352     *            {@code true} if this sort key should be evaluated in reverse
353     *            (descending) order.
354     * @param orderingMatchingRule
355     *            The name or OID of the ordering matching rule, which should be
356     *            used when comparing attributes using this sort key, or
357     *            {@code null} if the default ordering matching rule associated
358     *            with the attribute should be used.
359     * @throws NullPointerException
360     *             If {@code AttributeDescription} was {@code null}.
361     */
362    public SortKey(final AttributeDescription attributeDescription, final boolean isReverseOrder,
363            final MatchingRule orderingMatchingRule) {
364        Reject.ifNull(attributeDescription);
365        this.attributeDescription = attributeDescription.toString();
366        this.orderingMatchingRule =
367                orderingMatchingRule != null ? orderingMatchingRule.getNameOrOID() : null;
368        this.isReverseOrder = isReverseOrder;
369    }
370
371    /**
372     * Creates a new sort key using the provided attribute description. The
373     * returned sort key will compare attributes in ascending order using the
374     * default ordering matching rule associated with the attribute.
375     *
376     * @param attributeDescription
377     *            The name of the attribute to be sorted using this sort key.
378     * @throws NullPointerException
379     *             If {@code AttributeDescription} was {@code null}.
380     */
381    public SortKey(final String attributeDescription) {
382        this(attributeDescription, false, null);
383    }
384
385    /**
386     * Creates a new sort key using the provided attribute description. The
387     * returned sort key will compare attributes in the order specified using
388     * the default ordering matching rule associated with the attribute.
389     *
390     * @param attributeDescription
391     *            The name of the attribute to be sorted using this sort key.
392     * @param isReverseOrder
393     *            {@code true} if this sort key should be evaluated in reverse
394     *            (descending) order.
395     * @throws NullPointerException
396     *             If {@code AttributeDescription} was {@code null}.
397     */
398    public SortKey(final String attributeDescription, final boolean isReverseOrder) {
399        this(attributeDescription, isReverseOrder, null);
400    }
401
402    /**
403     * Creates a new sort key using the provided attribute description. The
404     * returned sort key will compare attributes in the order specified using
405     * the named ordering matching rule.
406     *
407     * @param attributeDescription
408     *            The name of the attribute to be sorted using this sort key.
409     * @param isReverseOrder
410     *            {@code true} if this sort key should be evaluated in reverse
411     *            (descending) order.
412     * @param orderingMatchingRule
413     *            The name or OID of the ordering matching rule, which should be
414     *            used when comparing attributes using this sort key, or
415     *            {@code null} if the default ordering matching rule associated
416     *            with the attribute should be used.
417     * @throws NullPointerException
418     *             If {@code AttributeDescription} was {@code null}.
419     */
420    public SortKey(final String attributeDescription, final boolean isReverseOrder,
421            final String orderingMatchingRule) {
422        Reject.ifNull(attributeDescription);
423        this.attributeDescription = attributeDescription;
424        this.orderingMatchingRule = orderingMatchingRule;
425        this.isReverseOrder = isReverseOrder;
426    }
427
428    /**
429     * Returns a {@code Comparator} which can be used to compare entries using
430     * this sort key. The attribute description and matching rule, if present,
431     * will be decoded using the default schema.
432     *
433     * @return The {@code Comparator}.
434     * @throws LocalizedIllegalArgumentException
435     *             If attributeDescription is not a valid LDAP string
436     *             representation of an attribute description, or if no ordering
437     *             matching rule was found.
438     */
439    public Comparator<Entry> comparator() {
440        return comparator(Schema.getDefaultSchema());
441    }
442
443    /**
444     * Returns a {@code Comparator} which can be used to compare entries using
445     * this sort key. The attribute description and matching rule, if present,
446     * will be decoded using the provided schema.
447     *
448     * @param schema
449     *            The schema which should be used for decoding the attribute
450     *            description and matching rule.
451     * @return The {@code Comparator}.
452     * @throws LocalizedIllegalArgumentException
453     *             If attributeDescription is not a valid LDAP string
454     *             representation of an attribute description, or if no ordering
455     *             matching rule was found.
456     * @throws NullPointerException
457     *             If {@code schema} was {@code null}.
458     */
459    public Comparator<Entry> comparator(final Schema schema) {
460        Reject.ifNull(schema);
461
462        final AttributeDescription ad = AttributeDescription.valueOf(attributeDescription, schema);
463
464        MatchingRule mrule;
465        if (orderingMatchingRule != null) {
466            // FIXME: need to check that the matching rule is a matching rule
467            // and can
468            // be used with the attribute.
469            mrule = schema.getMatchingRule(orderingMatchingRule);
470
471            if (mrule == null) {
472                // Specified ordering matching rule not found.
473                final LocalizableMessage message =
474                        ERR_SORT_KEY_MRULE_NOT_FOUND.get(toString(), orderingMatchingRule);
475                throw new LocalizedIllegalArgumentException(message);
476            }
477        } else {
478            mrule = ad.getAttributeType().getOrderingMatchingRule();
479
480            if (mrule == null) {
481                // No default ordering matching rule found.
482                final LocalizableMessage message =
483                        ERR_SORT_KEY_DEFAULT_MRULE_NOT_FOUND.get(toString(), attributeDescription);
484                throw new LocalizedIllegalArgumentException(message);
485            }
486        }
487
488        return new EntryComparator(ad, mrule, isReverseOrder);
489    }
490
491    /**
492     * Returns the name of the attribute to be sorted using this sort key.
493     *
494     * @return The name of the attribute to be sorted using this sort key.
495     */
496    public String getAttributeDescription() {
497        return attributeDescription;
498    }
499
500    /**
501     * Returns the name or OID of the ordering matching rule, if specified,
502     * which should be used when comparing attributes using this sort key.
503     *
504     * @return The name or OID of the ordering matching rule, if specified,
505     *         which should be used when comparing attributes using this sort
506     *         key, or {@code null} if the default ordering matching rule
507     *         associated with the attribute should be used.
508     */
509    public String getOrderingMatchingRule() {
510        return orderingMatchingRule;
511    }
512
513    /**
514     * Returns {@code true} if this sort key should be evaluated in reverse
515     * (descending) order. More specifically, comparisons performed using the
516     * ordering matching rule associated with this sort key will have their
517     * results inverted.
518     *
519     * @return {@code true} if this sort key should be evaluated in reverse
520     *         (descending) order.
521     */
522    public boolean isReverseOrder() {
523        return isReverseOrder;
524    }
525
526    /**
527     * Returns a string representation of this sort key using the format defined
528     * in {@link #valueOf(String)}.
529     *
530     * @return A string representation of this sort key.
531     */
532    @Override
533    public String toString() {
534        final StringBuilder builder = new StringBuilder();
535        if (isReverseOrder) {
536            builder.append('-');
537        }
538        builder.append(attributeDescription);
539        if (orderingMatchingRule != null) {
540            builder.append(':');
541            builder.append(orderingMatchingRule);
542        }
543        return builder.toString();
544    }
545
546}