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