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