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<Entry> comparator = SortKey.comparator("cn"); 061 * Set<SearchResultEntry>; results = new TreeSet<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}