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 2006-2010 Sun Microsystems, Inc.
015 * Portions Copyright 2011-2016 ForgeRock AS.
016 */
017package org.opends.server.types;
018
019import java.util.ArrayList;
020import java.util.Collection;
021import java.util.Collections;
022import java.util.HashSet;
023import java.util.InputMismatchException;
024import java.util.Iterator;
025import java.util.Map;
026import java.util.NoSuchElementException;
027import java.util.Objects;
028import java.util.Scanner;
029import java.util.Set;
030import java.util.TreeMap;
031import java.util.regex.Pattern;
032
033import org.forgerock.i18n.LocalizableMessage;
034import org.forgerock.opendj.ldap.DN;
035import org.forgerock.opendj.ldap.ResultCode;
036import org.forgerock.opendj.ldap.schema.ObjectClass;
037import org.opends.server.core.DirectoryServer;
038import org.opends.server.util.StaticUtils;
039
040import static org.opends.messages.SchemaMessages.*;
041
042/**
043 * An RFC 3672 subtree specification.
044 * <p>
045 * This implementation extends RFC 3672 by supporting search filters
046 * for specification filters. More specifically, the
047 * {@code Refinement} product has been extended as follows:
048 *
049 * <pre>
050 *  Refinement = item / and / or / not / Filter
051 *
052 *  Filter     = dquote *SafeUTF8Character dquote
053 * </pre>
054 *
055 * @see <a href="http://tools.ietf.org/html/rfc3672">RFC 3672 -
056 *      Subentries in the Lightweight Directory Access Protocol (LDAP)
057 *      </a>
058 */
059@org.opends.server.types.PublicAPI(
060    stability = org.opends.server.types.StabilityLevel.VOLATILE,
061    mayInstantiate = false,
062    mayExtend = true,
063    mayInvoke = false)
064public final class SubtreeSpecification
065{
066
067  /**
068   * RFC 3672 subtree specification AND refinement. This type of
069   * refinement filters entries based on all of the underlying
070   * refinements being <code>true</code>.
071   */
072  private static final class AndRefinement extends Refinement
073  {
074    /** The set of refinements which must all be true. */
075    private final Collection<Refinement> refinementSet;
076
077    /**
078     * Create a new AND refinement.
079     *
080     * @param refinementSet
081     *          The set of refinements which must all be
082     *          <code>true</code>.
083     */
084    private AndRefinement(final Collection<Refinement> refinementSet)
085    {
086      this.refinementSet = refinementSet;
087    }
088
089    @Override
090    public boolean equals(final Object obj)
091    {
092      if (this == obj)
093      {
094        return true;
095      }
096
097      if (obj instanceof AndRefinement)
098      {
099        final AndRefinement other = (AndRefinement) obj;
100
101        return refinementSet.equals(other.refinementSet);
102      }
103
104      return false;
105    }
106
107    @Override
108    public int hashCode()
109    {
110      return refinementSet.hashCode();
111    }
112
113    @Override
114    public boolean matches(final Entry entry)
115    {
116      for (final Refinement refinement : refinementSet)
117      {
118        if (!refinement.matches(entry))
119        {
120          return false;
121        }
122      }
123
124      // All sub-refinements matched.
125      return true;
126    }
127
128    @Override
129    public StringBuilder toString(final StringBuilder builder)
130    {
131      switch (refinementSet.size())
132      {
133      case 0:
134        // Do nothing.
135        break;
136      case 1:
137        refinementSet.iterator().next().toString(builder);
138        break;
139      default:
140        builder.append("and:{");
141        final Iterator<Refinement> iterator = refinementSet
142            .iterator();
143        iterator.next().toString(builder);
144        while (iterator.hasNext())
145        {
146          builder.append(", ");
147          iterator.next().toString(builder);
148        }
149        builder.append("}");
150        break;
151      }
152
153      return builder;
154    }
155  }
156
157  /** A refinement which uses a search filter. */
158  public static final class FilterRefinement extends Refinement
159  {
160    /** The search filter. */
161    private final SearchFilter filter;
162
163    /**
164     * Create a new filter refinement.
165     *
166     * @param filter
167     *          The search filter.
168     */
169    private FilterRefinement(final SearchFilter filter)
170    {
171      this.filter = filter;
172    }
173
174    @Override
175    public boolean equals(final Object obj)
176    {
177      if (this == obj)
178      {
179        return true;
180      }
181
182      if (obj instanceof FilterRefinement)
183      {
184        final FilterRefinement other = (FilterRefinement) obj;
185        return filter.equals(other.filter);
186      }
187
188      return false;
189    }
190
191    @Override
192    public int hashCode()
193    {
194      return filter.hashCode();
195    }
196
197    @Override
198    public boolean matches(final Entry entry)
199    {
200      try
201      {
202        return filter.matchesEntry(entry);
203      }
204      catch (final DirectoryException e)
205      {
206        // TODO: need to decide what to do with the exception here.
207        // It's probably safe to ignore, but we could log it perhaps.
208        return false;
209      }
210    }
211
212    @Override
213    public StringBuilder toString(final StringBuilder builder)
214    {
215      StaticUtils.toRFC3641StringValue(builder, filter.toString());
216      return builder;
217    }
218  }
219
220  /**
221   * RFC 3672 subtree specification Item refinement. This type of
222   * refinement filters entries based on the presence of a specified
223   * object class.
224   */
225  private static final class ItemRefinement extends Refinement
226  {
227    /** The item's object class. */
228    private final String objectClass;
229
230    /** The item's normalized object class. */
231    private final String normalizedObjectClass;
232
233    /**
234     * Create a new item refinement.
235     *
236     * @param objectClass
237     *          The item's object class.
238     */
239    private ItemRefinement(final String objectClass)
240    {
241      this.objectClass = objectClass;
242      this.normalizedObjectClass = StaticUtils
243          .toLowerCase(objectClass.trim());
244    }
245
246    @Override
247    public boolean equals(final Object obj)
248    {
249      if (this == obj)
250      {
251        return true;
252      }
253
254      if (obj instanceof ItemRefinement)
255      {
256        final ItemRefinement other = (ItemRefinement) obj;
257
258        return normalizedObjectClass
259            .equals(other.normalizedObjectClass);
260      }
261
262      return false;
263    }
264
265    @Override
266    public int hashCode()
267    {
268      return normalizedObjectClass.hashCode();
269    }
270
271    @Override
272    public boolean matches(final Entry entry)
273    {
274      final ObjectClass oc = DirectoryServer.getSchema().getObjectClass(normalizedObjectClass);
275      return !oc.isPlaceHolder() && entry.hasObjectClass(oc);
276    }
277
278    @Override
279    public StringBuilder toString(final StringBuilder builder)
280    {
281      builder.append("item:");
282      builder.append(objectClass);
283      return builder;
284    }
285  }
286
287  /**
288   * RFC 3672 subtree specification NOT refinement. This type of
289   * refinement filters entries based on the underlying refinement
290   * being <code>false</code>
291   * .
292   */
293  private static final class NotRefinement extends Refinement
294  {
295    /** The inverted refinement. */
296    private final Refinement refinement;
297
298    /**
299     * Create a new NOT refinement.
300     *
301     * @param refinement
302     *          The refinement which must be <code>false</code>.
303     */
304    private NotRefinement(final Refinement refinement)
305    {
306      this.refinement = refinement;
307    }
308
309    @Override
310    public boolean equals(final Object obj)
311    {
312      if (this == obj)
313      {
314        return true;
315      }
316
317      if (obj instanceof NotRefinement)
318      {
319        final NotRefinement other = (NotRefinement) obj;
320
321        return refinement.equals(other.refinement);
322      }
323
324      return false;
325    }
326
327    @Override
328    public int hashCode()
329    {
330      return refinement.hashCode();
331    }
332
333    @Override
334    public boolean matches(final Entry entry)
335    {
336      return !refinement.matches(entry);
337    }
338
339    @Override
340    public StringBuilder toString(final StringBuilder builder)
341    {
342      builder.append("not:");
343      return refinement.toString(builder);
344    }
345  }
346
347  /**
348   * RFC 3672 subtree specification OR refinement. This type of
349   * refinement filters entries based on at least one of the
350   * underlying refinements being <code>true</code>.
351   */
352  private static final class OrRefinement extends Refinement
353  {
354    /** The set of refinements of which at least one must be true. */
355    private final Collection<Refinement> refinementSet;
356
357    /**
358     * Create a new OR refinement.
359     *
360     * @param refinementSet
361     *          The set of refinements of which at least one must be
362     *          <code>true</code>.
363     */
364    private OrRefinement(final Collection<Refinement> refinementSet)
365    {
366      this.refinementSet = refinementSet;
367    }
368
369    @Override
370    public boolean equals(final Object obj)
371    {
372      if (this == obj)
373      {
374        return true;
375      }
376
377      if (obj instanceof AndRefinement)
378      {
379        final AndRefinement other = (AndRefinement) obj;
380
381        return refinementSet.equals(other.refinementSet);
382      }
383
384      return false;
385    }
386
387    @Override
388    public int hashCode()
389    {
390      return refinementSet.hashCode();
391    }
392
393    @Override
394    public boolean matches(final Entry entry)
395    {
396      for (final Refinement refinement : refinementSet)
397      {
398        if (refinement.matches(entry))
399        {
400          return true;
401        }
402      }
403
404      // No sub-refinements matched.
405      return false;
406    }
407
408    @Override
409    public StringBuilder toString(final StringBuilder builder)
410    {
411      switch (refinementSet.size())
412      {
413      case 0:
414        // Do nothing.
415        break;
416      case 1:
417        refinementSet.iterator().next().toString(builder);
418        break;
419      default:
420        builder.append("or:{");
421        final Iterator<Refinement> iterator = refinementSet
422            .iterator();
423        iterator.next().toString(builder);
424        while (iterator.hasNext())
425        {
426          builder.append(", ");
427          iterator.next().toString(builder);
428        }
429        builder.append("}");
430        break;
431      }
432
433      return builder;
434    }
435  }
436
437  /** Abstract interface for RFC3672 specification filter refinements. */
438  private static abstract class Refinement
439  {
440    /** Create a new RFC3672 specification filter refinement. */
441    protected Refinement()
442    {
443      // No implementation required.
444    }
445
446    @Override
447    public abstract boolean equals(Object obj);
448
449    @Override
450    public abstract int hashCode();
451
452    /**
453     * Check if the refinement matches the given entry.
454     *
455     * @param entry
456     *          The filterable entry.
457     * @return Returns <code>true</code> if the entry matches the
458     *         refinement, or <code>false</code> otherwise.
459     */
460    public abstract boolean matches(Entry entry);
461
462    @Override
463    public final String toString()
464    {
465      final StringBuilder builder = new StringBuilder();
466
467      return toString(builder).toString();
468    }
469
470    /**
471     * Append the string representation of the refinement to the
472     * provided strin builder.
473     *
474     * @param builder
475     *          The string builder.
476     * @return The string builder.
477     */
478    public abstract StringBuilder toString(StringBuilder builder);
479  }
480
481  /**
482   * Internal utility class which can be used by sub-classes to help
483   * parse string representations.
484   */
485  private static final class Parser
486  {
487    /** Text scanner used to parse the string value. */
488    private final Scanner scanner;
489
490    /** Pattern used to detect left braces. */
491    private static final Pattern LBRACE = Pattern.compile("\\{.*");
492    /** Pattern used to parse left braces. */
493    private static final Pattern LBRACE_TOKEN = Pattern.compile("\\{");
494    /** Pattern used to detect right braces. */
495    private static final Pattern RBRACE = Pattern.compile("\\}.*");
496    /** Pattern used to parse right braces. */
497    private static final Pattern RBRACE_TOKEN = Pattern.compile("\\}");
498    /** Pattern used to detect comma separators. */
499    private static final Pattern SEP = Pattern.compile(",.*");
500    /** Pattern used to parse comma separators. */
501    private static final Pattern SEP_TOKEN = Pattern.compile(",");
502    /** Pattern used to detect colon separators. */
503    private static final Pattern COLON = Pattern.compile(":.*");
504    /** Pattern used to parse colon separators. */
505    private static final Pattern COLON_TOKEN = Pattern.compile(":");
506    /** Pattern used to detect integer values. */
507    private static final Pattern INT = Pattern.compile("\\d.*");
508    /** Pattern used to parse integer values. */
509    private static final Pattern INT_TOKEN = Pattern.compile("\\d+");
510    /** Pattern used to detect name values. */
511    private static final Pattern NAME = Pattern.compile("[\\w_;-].*");
512    /** Pattern used to parse name values. */
513    private static final Pattern NAME_TOKEN = Pattern.compile("[\\w_;-]+");
514    /** Pattern used to detect RFC3641 string values. */
515    private static final Pattern STRING_VALUE = Pattern.compile("\".*");
516    /** Pattern used to parse RFC3641 string values. */
517    private static final Pattern STRING_VALUE_TOKEN = Pattern
518        .compile("\"([^\"]|(\"\"))*\"");
519
520    /**
521     * Create a new parser for a subtree specification string value.
522     *
523     * @param value
524     *          The subtree specification string value.
525     */
526    private Parser(final String value)
527    {
528      this.scanner = new Scanner(value);
529    }
530
531    /**
532     * Determine if there are remaining tokens.
533     *
534     * @return <code>true</code> if and only if there are remaining
535     *         tokens.
536     */
537    private boolean hasNext()
538    {
539      return scanner.hasNext();
540    }
541
542    /**
543     * Determine if the next token is a right-brace character.
544     *
545     * @return <code>true</code> if and only if the next token is a
546     *         valid right brace character.
547     */
548    private boolean hasNextRightBrace()
549    {
550      return scanner.hasNext(RBRACE);
551    }
552
553    /**
554     * Scans the next token of the input as a non-negative
555     * <code>int</code> value.
556     *
557     * @return The name value scanned from the input.
558     * @throws InputMismatchException
559     *           If the next token is not a valid non-negative integer
560     *           string.
561     * @throws NoSuchElementException
562     *           If input is exhausted.
563     */
564    private int nextInt() throws InputMismatchException,
565        NoSuchElementException
566    {
567      final String s = nextValue(INT, INT_TOKEN);
568      return Integer.parseInt(s);
569    }
570
571    /**
572     * Scans the next token of the input as a key value.
573     *
574     * @return The lower-case key value scanned from the input.
575     * @throws InputMismatchException
576     *           If the next token is not a valid key string.
577     * @throws NoSuchElementException
578     *           If input is exhausted.
579     */
580    private String nextKey() throws InputMismatchException,
581        NoSuchElementException
582    {
583      return StaticUtils.toLowerCase(scanner.next());
584    }
585
586    /**
587     * Scans the next token of the input as a name value.
588     * <p>
589     * A name is any string containing only alpha-numeric characters
590     * or hyphens, semi-colons, or underscores.
591     *
592     * @return The name value scanned from the input.
593     * @throws InputMismatchException
594     *           If the next token is not a valid name string.
595     * @throws NoSuchElementException
596     *           If input is exhausted.
597     */
598    private String nextName() throws InputMismatchException,
599        NoSuchElementException
600    {
601      return nextValue(NAME, NAME_TOKEN);
602    }
603
604    /**
605     * Scans the next tokens of the input as a set of specific
606     * exclusions encoded according to the SpecificExclusion
607     * production in RFC 3672.
608     *
609     * @param chopBefore
610     *          The set of chop before local names.
611     * @param chopAfter
612     *          The set of chop after local names.
613     * @throws InputMismatchException
614     *           If the common component did not have a valid syntax.
615     * @throws NoSuchElementException
616     *           If input is exhausted.
617     * @throws DirectoryException
618     *           If an error occurred when attempting to parse a
619     *           DN value.
620     */
621    private void nextSpecificExclusions(final Set<DN> chopBefore,
622        final Set<DN> chopAfter) throws InputMismatchException,
623        NoSuchElementException, DirectoryException
624    {
625      // Skip leading open-brace.
626      skipLeftBrace();
627
628      // Parse each chop DN in the sequence.
629      boolean isFirstValue = true;
630      while (true)
631      {
632        // Make sure that there is a closing brace.
633        if (hasNextRightBrace())
634        {
635          skipRightBrace();
636          break;
637        }
638
639        // Make sure that there is a comma separator if this is not
640        // the first element.
641        if (!isFirstValue)
642        {
643          skipSeparator();
644        }
645        else
646        {
647          isFirstValue = false;
648        }
649
650        // Parse each chop specification which is of the form
651        // <type>:<value>.
652        final String type = StaticUtils.toLowerCase(nextName());
653        skipColon();
654        if ("chopbefore".equals(type))
655        {
656          chopBefore.add(DN.valueOf(nextStringValue()));
657        }
658        else if ("chopafter".equals(type))
659        {
660          chopAfter.add(DN.valueOf(nextStringValue()));
661        }
662        else
663        {
664          throw new java.util.InputMismatchException();
665        }
666      }
667    }
668
669    /**
670     * Scans the next token of the input as a string quoted according
671     * to the StringValue production in RFC 3641.
672     * <p>
673     * The return string has its outer double quotes removed and any
674     * escape inner double quotes unescaped.
675     *
676     * @return The string value scanned from the input.
677     * @throws InputMismatchException
678     *           If the next token is not a valid string.
679     * @throws NoSuchElementException
680     *           If input is exhausted.
681     */
682    private String nextStringValue() throws InputMismatchException,
683        NoSuchElementException
684    {
685      final String s = nextValue(STRING_VALUE, STRING_VALUE_TOKEN);
686      return s.substring(1, s.length() - 1).replace("\"\"", "\"");
687    }
688
689    /**
690     * Skip a colon separator.
691     *
692     * @throws InputMismatchException
693     *           If the next token is not a colon separator character.
694     * @throws NoSuchElementException
695     *           If input is exhausted.
696     */
697    private void skipColon() throws InputMismatchException,
698        NoSuchElementException
699    {
700      nextValue(COLON, COLON_TOKEN);
701    }
702
703    /**
704     * Skip a left-brace character.
705     *
706     * @throws InputMismatchException
707     *           If the next token is not a left-brace character.
708     * @throws NoSuchElementException
709     *           If input is exhausted.
710     */
711    private void skipLeftBrace() throws InputMismatchException,
712        NoSuchElementException
713    {
714      nextValue(LBRACE, LBRACE_TOKEN);
715    }
716
717    /**
718     * Skip a right-brace character.
719     *
720     * @throws InputMismatchException
721     *           If the next token is not a right-brace character.
722     * @throws NoSuchElementException
723     *           If input is exhausted.
724     */
725    private void skipRightBrace() throws InputMismatchException,
726        NoSuchElementException
727    {
728      nextValue(RBRACE, RBRACE_TOKEN);
729    }
730
731    /**
732     * Skip a comma separator.
733     *
734     * @throws InputMismatchException
735     *           If the next token is not a comma separator character.
736     * @throws NoSuchElementException
737     *           If input is exhausted.
738     */
739    private void skipSeparator() throws InputMismatchException,
740        NoSuchElementException
741    {
742      nextValue(SEP, SEP_TOKEN);
743    }
744
745    /**
746     * Parse the next token from the string using the specified
747     * patterns.
748     *
749     * @param head
750     *          The pattern used to determine if the next token is a
751     *          possible match.
752     * @param content
753     *          The pattern used to parse the token content.
754     * @return The next token matching the <code>content</code>
755     *         pattern.
756     * @throws InputMismatchException
757     *           If the next token does not match the
758     *           <code>content</code> pattern.
759     * @throws NoSuchElementException
760     *           If input is exhausted.
761     */
762    private String nextValue(final Pattern head,
763        final Pattern content)
764        throws InputMismatchException, NoSuchElementException
765    {
766      if (!scanner.hasNext())
767      {
768        throw new java.util.NoSuchElementException();
769      }
770
771      if (!scanner.hasNext(head))
772      {
773        throw new java.util.InputMismatchException();
774      }
775
776      final String s = scanner.findInLine(content);
777      if (s == null)
778      {
779        throw new java.util.InputMismatchException();
780      }
781
782      return s;
783    }
784  }
785
786  /**
787   * Parses the string argument as an RFC3672 subtree specification.
788   *
789   * @param rootDN
790   *          The DN of the subtree specification's base entry.
791   * @param s
792   *          The string to be parsed.
793   * @return The RFC3672 subtree specification represented by the
794   *         string argument.
795   * @throws DirectoryException
796   *           If the string does not contain a parsable relative
797   *           subtree specification.
798   */
799  public static SubtreeSpecification valueOf(final DN rootDN,
800      final String s) throws DirectoryException
801  {
802    // Default values.
803    DN relativeBaseDN = null;
804
805    int minimum = -1;
806    int maximum = -1;
807
808    final HashSet<DN> chopBefore = new HashSet<>();
809    final HashSet<DN> chopAfter = new HashSet<>();
810
811    Refinement refinement = null;
812
813    // Value must have an opening left brace.
814    final Parser parser = new Parser(s);
815    boolean isValid = true;
816
817    try
818    {
819      parser.skipLeftBrace();
820
821      // Parse each element of the value sequence.
822      boolean isFirst = true;
823
824      while (true)
825      {
826        if (parser.hasNextRightBrace())
827        {
828          // Make sure that there is a closing brace and no trailing text.
829          parser.skipRightBrace();
830
831          if (parser.hasNext())
832          {
833            throw new java.util.InputMismatchException();
834          }
835          break;
836        }
837
838        // Make sure that there is a comma separator if this is not
839        // the first element.
840        if (!isFirst)
841        {
842          parser.skipSeparator();
843        }
844        else
845        {
846          isFirst = false;
847        }
848
849        final String key = parser.nextKey();
850        if ("base".equals(key))
851        {
852          if (relativeBaseDN != null)
853          {
854            // Relative base DN specified more than once.
855            throw new InputMismatchException();
856          }
857          relativeBaseDN = DN.valueOf(parser.nextStringValue());
858        }
859        else if ("minimum".equals(key))
860        {
861          if (minimum != -1)
862          {
863            // Minimum specified more than once.
864            throw new InputMismatchException();
865          }
866          minimum = parser.nextInt();
867        }
868        else if ("maximum".equals(key))
869        {
870          if (maximum != -1)
871          {
872            // Maximum specified more than once.
873            throw new InputMismatchException();
874          }
875          maximum = parser.nextInt();
876        }
877        else if ("specificationfilter".equals(key))
878        {
879          if (refinement != null)
880          {
881            // Refinements specified more than once.
882            throw new InputMismatchException();
883          }
884
885          // First try normal search filter before RFC3672 refinements.
886          try
887          {
888            final SearchFilter filter = SearchFilter
889                .createFilterFromString(parser.nextStringValue());
890            refinement = new FilterRefinement(filter);
891          }
892          catch (final InputMismatchException e)
893          {
894            refinement = parseRefinement(parser);
895          }
896        }
897        else if ("specificexclusions".equals(key))
898        {
899          if (!chopBefore.isEmpty() || !chopAfter.isEmpty())
900          {
901            // Specific exclusions specified more than once.
902            throw new InputMismatchException();
903          }
904
905          parser.nextSpecificExclusions(chopBefore, chopAfter);
906        }
907        else
908        {
909          throw new InputMismatchException();
910        }
911      }
912
913      // Make default minimum value is 0.
914      if (minimum < 0)
915      {
916        minimum = 0;
917      }
918
919      // Check that the maximum, if specified, is gte the minimum.
920      if (maximum >= 0 && maximum < minimum)
921      {
922        isValid = false;
923      }
924    }
925    catch (final NoSuchElementException e)
926    {
927      isValid = false;
928    }
929
930    if (!isValid)
931    {
932      final LocalizableMessage message =
933        ERR_ATTR_SYNTAX_RFC3672_SUBTREE_SPECIFICATION_INVALID.get(s);
934      throw new DirectoryException(
935          ResultCode.INVALID_ATTRIBUTE_SYNTAX, message);
936    }
937    return new SubtreeSpecification(rootDN, relativeBaseDN, minimum, maximum, chopBefore, chopAfter, refinement);
938  }
939
940  /**
941   * Parse a single refinement.
942   *
943   * @param parser
944   *          The active subtree specification parser.
945   * @return The parsed refinement.
946   * @throws InputMismatchException
947   *           If the common component did not have a valid syntax.
948   * @throws NoSuchElementException
949   *           If input is exhausted.
950   */
951  private static Refinement parseRefinement(final Parser parser)
952      throws InputMismatchException, NoSuchElementException
953  {
954    // Get the type of refinement.
955    final String type = StaticUtils.toLowerCase(parser.nextName());
956
957    // Skip the colon separator.
958    parser.skipColon();
959
960    if ("item".equals(type))
961    {
962      return new ItemRefinement(parser.nextName());
963    }
964    else if ("not".equals(type))
965    {
966      return new NotRefinement(parseRefinement(parser));
967    }
968    else if ("and".equals(type))
969    {
970      return new AndRefinement(parseRefinementSet(parser));
971    }
972    else if ("or".equals(type))
973    {
974      return new OrRefinement(parseRefinementSet(parser));
975    }
976    else
977    {
978      // Unknown refinement type.
979      throw new InputMismatchException();
980    }
981  }
982
983  /**
984   * Parse a list of refinements.
985   *
986   * @param parser
987   *          The active subtree specification parser.
988   * @return The parsed refinement list.
989   * @throws InputMismatchException
990   *           If the common component did not have a valid syntax.
991   * @throws NoSuchElementException
992   *           If input is exhausted.
993   */
994  private static ArrayList<Refinement> parseRefinementSet(
995      final Parser parser) throws InputMismatchException,
996      NoSuchElementException
997  {
998    final ArrayList<Refinement> refinements = new ArrayList<>();
999
1000    // Skip leading open-brace.
1001    parser.skipLeftBrace();
1002
1003    // Parse each chop DN in the sequence.
1004    boolean isFirstValue = true;
1005    while (true)
1006    {
1007      // Make sure that there is a closing brace.
1008      if (parser.hasNextRightBrace())
1009      {
1010        parser.skipRightBrace();
1011        break;
1012      }
1013
1014      // Make sure that there is a comma separator if this is not
1015      // the first element.
1016      if (!isFirstValue)
1017      {
1018        parser.skipSeparator();
1019      }
1020      else
1021      {
1022        isFirstValue = false;
1023      }
1024
1025      // Parse each sub-refinement.
1026      refinements.add(parseRefinement(parser));
1027    }
1028
1029    return refinements;
1030  }
1031
1032  /** The absolute base of the subtree. */
1033  private final DN baseDN;
1034
1035  /** Optional minimum depth (<=0 means unlimited). */
1036  private final int minimumDepth;
1037  /** Optional maximum depth (<0 means unlimited). */
1038  private final int maximumDepth;
1039
1040  /** Optional set of chop before absolute DNs (mapping to their local-names). */
1041  private final Map<DN, DN> chopBefore;
1042  /** Optional set of chop after absolute DNs (mapping to their local-names). */
1043  private final Map<DN, DN> chopAfter;
1044
1045  /** The root DN. */
1046  private final DN rootDN;
1047  /** The optional relative base DN. */
1048  private final DN relativeBaseDN;
1049
1050  /** The optional specification filter refinements. */
1051  private final Refinement refinements;
1052
1053  /**
1054   * Create a new RFC3672 subtree specification.
1055   *
1056   * @param rootDN
1057   *          The root DN of the subtree.
1058   * @param relativeBaseDN
1059   *          The relative base DN (or {@code null} if not
1060   *          specified).
1061   * @param minimumDepth
1062   *          The minimum depth (less than or equal to 0 means unlimited).
1063   * @param maximumDepth
1064   *          The maximum depth (less than 0 means unlimited).
1065   * @param chopBefore
1066   *          The set of chop before local names (relative to the
1067   *          relative base DN), or {@code null} if there are
1068   *          none.
1069   * @param chopAfter
1070   *          The set of chop after local names (relative to the
1071   *          relative base DN), or {@code null} if there are
1072   *          none.
1073   * @param refinements
1074   *          The optional specification filter refinements, or
1075   *          {@code null} if there are none.
1076   */
1077  public SubtreeSpecification(final DN rootDN,
1078      final DN relativeBaseDN, final int minimumDepth,
1079      final int maximumDepth, final Iterable<DN> chopBefore,
1080      final Iterable<DN> chopAfter, final Refinement refinements)
1081  {
1082    this.baseDN = relativeBaseDN == null ? rootDN : rootDN
1083        .child(relativeBaseDN);
1084    this.minimumDepth = minimumDepth;
1085    this.maximumDepth = maximumDepth;
1086
1087    if (chopBefore != null && chopBefore.iterator().hasNext())
1088    {
1089      // Calculate the absolute DNs.
1090      final TreeMap<DN, DN> map = new TreeMap<>();
1091      for (final DN localName : chopBefore)
1092      {
1093        map.put(baseDN.child(localName), localName);
1094      }
1095      this.chopBefore = Collections.unmodifiableMap(map);
1096    }
1097    else
1098    {
1099      // No chop before specifications.
1100      this.chopBefore = Collections.emptyMap();
1101    }
1102
1103    if (chopAfter != null && chopAfter.iterator().hasNext())
1104    {
1105      // Calculate the absolute DNs.
1106      final TreeMap<DN, DN> map = new TreeMap<>();
1107      for (final DN localName : chopAfter)
1108      {
1109        map.put(baseDN.child(localName), localName);
1110      }
1111      this.chopAfter = Collections.unmodifiableMap(map);
1112    }
1113    else
1114    {
1115      // No chop after specifications.
1116      this.chopAfter = Collections.emptyMap();
1117    }
1118
1119    this.rootDN = rootDN;
1120    this.relativeBaseDN = relativeBaseDN;
1121    this.refinements = refinements;
1122  }
1123
1124  /**
1125   * Indicates whether the provided object is logically equal to this
1126   * subtree specification object.
1127   *
1128   * @param obj
1129   *          The object for which to make the determination.
1130   * @return {@code true} if the provided object is logically equal
1131   *         to this subtree specification object, or {@code false}
1132   *         if not.
1133   */
1134  @Override
1135  public boolean equals(final Object obj)
1136  {
1137    if (this == obj)
1138    {
1139      return true;
1140    }
1141
1142    if (obj instanceof SubtreeSpecification)
1143    {
1144      final SubtreeSpecification other = (SubtreeSpecification) obj;
1145
1146      return minimumDepth == other.minimumDepth
1147          && maximumDepth == other.maximumDepth
1148          && chopBefore.values().equals(other.chopBefore.values())
1149          && chopAfter.values().equals(other.chopAfter.values())
1150          && getBaseDN().equals(other.getBaseDN())
1151          && Objects.equals(refinements, other.refinements);
1152    }
1153
1154    return false;
1155  }
1156
1157  /**
1158   * Get the absolute base DN of the subtree specification.
1159   *
1160   * @return Returns the absolute base DN of the subtree
1161   *         specification.
1162   */
1163  public DN getBaseDN()
1164  {
1165    return baseDN;
1166  }
1167
1168  /**
1169   * Get the set of chop after relative DNs.
1170   *
1171   * @return Returns the set of chop after relative DNs.
1172   */
1173  public Iterable<DN> getChopAfter()
1174  {
1175    return chopAfter.values();
1176  }
1177
1178  /**
1179   * Get the set of chop before relative DNs.
1180   *
1181   * @return Returns the set of chop before relative DNs.
1182   */
1183  public Iterable<DN> getChopBefore()
1184  {
1185    return chopBefore.values();
1186  }
1187
1188  /**
1189   * Get the maximum depth of the subtree specification.
1190   *
1191   * @return Returns the maximum depth (less than 0 indicates unlimited depth).
1192   */
1193  public int getMaximumDepth()
1194  {
1195    return maximumDepth;
1196  }
1197
1198  /**
1199   * Get the minimum depth of the subtree specification.
1200   *
1201   * @return Returns the minimum depth (<=0 indicates unlimited
1202   *         depth).
1203   */
1204  public int getMinimumDepth()
1205  {
1206    return minimumDepth;
1207  }
1208
1209  /**
1210   * Get the specification filter refinements.
1211   *
1212   * @return Returns the specification filter refinements, or
1213   *         <code>null</code> if none were specified.
1214   */
1215  public Refinement getRefinements()
1216  {
1217    return refinements;
1218  }
1219
1220  /**
1221   * Get the relative base DN.
1222   *
1223   * @return Returns the relative base DN or <code>null</code> if
1224   *         none was specified.
1225   */
1226  public DN getRelativeBaseDN()
1227  {
1228    return relativeBaseDN;
1229  }
1230
1231  /**
1232   * Get the root DN.
1233   *
1234   * @return Returns the root DN.
1235   */
1236  public DN getRootDN()
1237  {
1238    return rootDN;
1239  }
1240
1241  /**
1242   * Retrieves the hash code for this subtree specification object.
1243   *
1244   * @return The hash code for this subtree specification object.
1245   */
1246  @Override
1247  public int hashCode()
1248  {
1249    int hash = minimumDepth * 31 + maximumDepth;
1250    hash = hash * 31 + chopBefore.values().hashCode();
1251    hash = hash * 31 + chopAfter.values().hashCode();
1252    hash = hash * 31 + getBaseDN().hashCode();
1253
1254    if (refinements != null)
1255    {
1256      hash = hash * 31 + refinements.hashCode();
1257    }
1258
1259    return hash;
1260  }
1261
1262  /**
1263   * Determine if the specified DN is within the scope of the subtree
1264   * specification.
1265   *
1266   * @param dn
1267   *          The distinguished name.
1268   * @return Returns <code>true</code> if the DN is within the scope
1269   *         of the subtree specification, or <code>false</code>
1270   *         otherwise.
1271   */
1272  public boolean isDNWithinScope(final DN dn)
1273  {
1274    if (!dn.isSubordinateOrEqualTo(baseDN))
1275    {
1276      return false;
1277    }
1278
1279    // Check minimum and maximum depths.
1280    final int baseRDNCount = baseDN.size();
1281
1282    if (minimumDepth > 0)
1283    {
1284      final int entryRDNCount = dn.size();
1285
1286      if (entryRDNCount - baseRDNCount < minimumDepth)
1287      {
1288        return false;
1289      }
1290    }
1291
1292    if (maximumDepth >= 0)
1293    {
1294      final int entryRDNCount = dn.size();
1295
1296      if (entryRDNCount - baseRDNCount > maximumDepth)
1297      {
1298        return false;
1299      }
1300    }
1301
1302    // Check exclusions.
1303    for (final DN chopBeforeDN : chopBefore.keySet())
1304    {
1305      if (dn.isSubordinateOrEqualTo(chopBeforeDN))
1306      {
1307        return false;
1308      }
1309    }
1310
1311    for (final DN chopAfterDN : chopAfter.keySet())
1312    {
1313      if (!dn.equals(chopAfterDN) && dn.isSubordinateOrEqualTo(chopAfterDN))
1314      {
1315        return false;
1316      }
1317    }
1318
1319    // Everything seemed to match.
1320    return true;
1321  }
1322
1323  /**
1324   * Determine if an entry is within the scope of the subtree
1325   * specification.
1326   *
1327   * @param entry
1328   *          The entry.
1329   * @return {@code true} if the entry is within the scope of the
1330   *         subtree specification, or {@code false} if not.
1331   */
1332  public boolean isWithinScope(final Entry entry)
1333  {
1334    return isDNWithinScope(entry.getName())
1335        && (refinements == null || refinements.matches(entry));
1336  }
1337
1338  /**
1339   * Retrieves a string representation of this subtree specification
1340   * object.
1341   *
1342   * @return A string representation of this subtree specification
1343   *         object.
1344   */
1345  @Override
1346  public String toString()
1347  {
1348    final StringBuilder builder = new StringBuilder();
1349    return toString(builder).toString();
1350  }
1351
1352  /**
1353   * Append the string representation of the subtree specification to
1354   * the provided string builder.
1355   *
1356   * @param builder
1357   *          The string builder.
1358   * @return The string builder.
1359   */
1360  public StringBuilder toString(final StringBuilder builder)
1361  {
1362    boolean isFirstElement = true;
1363
1364    // Output the optional base DN.
1365    builder.append("{");
1366    if (relativeBaseDN != null && !relativeBaseDN.isRootDN())
1367    {
1368      builder.append(" base ");
1369      StaticUtils.toRFC3641StringValue(builder, relativeBaseDN.toString());
1370      isFirstElement = false;
1371    }
1372
1373    // Output the optional specific exclusions.
1374    final Iterable<DN> chopBefore = getChopBefore();
1375    final Iterable<DN> chopAfter = getChopAfter();
1376
1377    if (chopBefore.iterator().hasNext()
1378        || chopAfter.iterator().hasNext())
1379    {
1380      isFirstElement = append2(builder, isFirstElement, " specificExclusions { ");
1381
1382      boolean isFirst = true;
1383
1384      for (final DN dn : chopBefore)
1385      {
1386        isFirst = append(builder, isFirst, "chopBefore:");
1387        StaticUtils.toRFC3641StringValue(builder, dn.toString());
1388      }
1389
1390      for (final DN dn : chopAfter)
1391      {
1392        isFirst = append(builder, isFirst, "chopAfter:");
1393        StaticUtils.toRFC3641StringValue(builder, dn.toString());
1394      }
1395
1396      builder.append(" }");
1397    }
1398
1399    // Output the optional minimum depth.
1400    if (getMinimumDepth() > 0)
1401    {
1402      isFirstElement = append2(builder, isFirstElement, " minimum ");
1403      builder.append(getMinimumDepth());
1404    }
1405
1406    // Output the optional maximum depth.
1407    if (getMaximumDepth() >= 0)
1408    {
1409      isFirstElement = append2(builder, isFirstElement, " maximum ");
1410      builder.append(getMaximumDepth());
1411    }
1412
1413    // Output the optional refinements.
1414    if (refinements != null)
1415    {
1416      isFirstElement = append2(builder, isFirstElement, " specificationFilter ");
1417      refinements.toString(builder);
1418    }
1419
1420    builder.append(" }");
1421
1422    return builder;
1423  }
1424
1425  private boolean append2(final StringBuilder builder, boolean isFirst, String toAppend)
1426  {
1427    if (isFirst)
1428    {
1429      isFirst = false;
1430    }
1431    else
1432    {
1433      builder.append(",");
1434    }
1435    builder.append(toAppend);
1436    return isFirst;
1437  }
1438
1439  private boolean append(final StringBuilder builder, boolean isFirst, String toAppend)
1440  {
1441    if (isFirst)
1442    {
1443      isFirst = false;
1444    }
1445    else
1446    {
1447      builder.append(", ");
1448    }
1449    builder.append(toAppend);
1450    return isFirst;
1451  }
1452}