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 2008 Sun Microsystems, Inc.
015 * Portions Copyright 2014-2016 ForgeRock AS.
016 */
017package org.opends.server.authorization.dseecompat;
018
019import static org.opends.messages.AccessControlMessages.*;
020import static org.opends.messages.SchemaMessages.*;
021import static org.opends.server.util.CollectionUtils.*;
022import static org.opends.server.util.StaticUtils.*;
023
024import java.util.ArrayList;
025import java.util.Arrays;
026import java.util.Iterator;
027import java.util.List;
028
029import org.forgerock.i18n.LocalizableMessage;
030import org.forgerock.i18n.slf4j.LocalizedLogger;
031import org.forgerock.opendj.ldap.ByteString;
032import org.forgerock.opendj.ldap.DN;
033import org.forgerock.opendj.ldap.ResultCode;
034import org.forgerock.util.Reject;
035import org.opends.server.types.DirectoryException;
036
037/**
038 * This class is used to encapsulate DN pattern matching using wildcards.
039 * The following wildcard uses are supported.
040 *
041 * Value substring:  Any number of wildcards may appear in RDN attribute
042 * values where they match zero or more characters, just like substring filters:
043 *   uid=b*jensen*
044 *
045 * Whole-Type:  A single wildcard may also be used to match any RDN attribute
046 * type, and the wildcard in this case may be omitted as a shorthand:
047 *   *=bjensen
048 *   bjensen
049 *
050 * Whole-RDN.  A single wildcard may be used to match exactly one RDN component
051 * (which may be single or multi-valued):
052 *   *,dc=example,dc=com
053 *
054 * Multiple-Whole-RDN:  A double wildcard may be used to match one or more
055 * RDN components:
056 *   uid=bjensen,**,dc=example,dc=com
057 */
058public class PatternDN
059{
060  private static final LocalizedLogger logger = LocalizedLogger.getLoggerForThisClass();
061
062  /**
063   * If the pattern did not include any Multiple-Whole-RDN wildcards, then this
064   * is the sequence of RDN patterns in the DN pattern.  Otherwise it is null.
065   */
066  private PatternRDN[] equality;
067
068  /**
069   * If the pattern included any Multiple-Whole-RDN wildcards, then these
070   * are the RDN pattern sequences that appear between those wildcards.
071   */
072  private PatternRDN[] subInitial;
073  private List<PatternRDN[]> subAnyElements;
074  private PatternRDN[] subFinal;
075
076  /**
077   * When there is no initial sequence, this is used to distinguish between
078   * the case where we have a suffix pattern (zero or more RDN components
079   * allowed before matching elements) and the case where it is not a
080   * suffix pattern but the pattern started with a Multiple-Whole-RDN wildcard
081   * (one or more RDN components allowed before matching elements).
082   */
083  private boolean isSuffix;
084
085  /**
086   * Create a DN pattern that does not include any Multiple-Whole-RDN wildcards.
087   * @param equality The sequence of RDN patterns making up the DN pattern.
088   */
089  private PatternDN(PatternRDN... equality)
090  {
091    this.equality = equality;
092  }
093
094  /**
095   * Create a DN pattern that includes Multiple-Whole-RDN wildcards.
096   * @param subInitial     The sequence of RDN patterns appearing at the
097   *                       start of the DN, or null if there are none.
098   * @param subAnyElements The list of sequences of RDN patterns appearing
099   *                       in order anywhere in the DN.
100   * @param subFinal       The sequence of RDN patterns appearing at the
101   *                       end of the DN, or null if there are none.
102   */
103  private PatternDN(PatternRDN[] subInitial,
104                    List<PatternRDN[]> subAnyElements,
105                    PatternRDN[] subFinal)
106  {
107    Reject.ifNull(subAnyElements);
108    this.subInitial = subInitial;
109    this.subAnyElements = subAnyElements;
110    this.subFinal = subFinal;
111  }
112
113  /**
114   * Determine whether a given DN matches this pattern.
115   * @param dn The DN to be matched.
116   * @return true if the DN matches the pattern.
117   */
118  public boolean matchesDN(DN dn)
119  {
120    return equality != null ? equalityMatchDN(dn) : substringMatchDN(dn);
121  }
122
123  private boolean equalityMatchDN(DN dn)
124  {
125    // There are no Multiple-Whole-RDN wildcards in the pattern.
126    if (equality.length != dn.size())
127    {
128      return false;
129    }
130
131    for (int i = 0; i < dn.size(); i++)
132    {
133      if (!equality[i].matchesRDN(dn.rdn(i)))
134      {
135        return false;
136      }
137    }
138
139    return true;
140  }
141
142  private boolean substringMatchDN(DN dn)
143  {
144    // There are Multiple-Whole-RDN wildcards in the pattern.
145    int valueLength = dn.size();
146
147    int pos = 0;
148    if (subInitial != null)
149    {
150      int initialLength = subInitial.length;
151      if (initialLength > valueLength)
152      {
153        return false;
154      }
155
156      for (; pos < initialLength; pos++)
157      {
158        if (!subInitial[pos].matchesRDN(dn.rdn(pos)))
159        {
160          return false;
161        }
162      }
163      pos++;
164    }
165    else if (!isSuffix)
166    {
167      pos++;
168    }
169
170    if (subAnyElements != null && ! subAnyElements.isEmpty())
171    {
172      for (PatternRDN[] element : subAnyElements)
173      {
174        int anyLength = element.length;
175
176        int end = valueLength - anyLength;
177        boolean match = false;
178        for (; pos < end; pos++)
179        {
180          if (element[0].matchesRDN(dn.rdn(pos))
181              && subMatch(dn, pos, element, anyLength))
182          {
183            match = true;
184            break;
185          }
186        }
187
188        if (!match)
189        {
190          return false;
191        }
192        pos += anyLength + 1;
193      }
194    }
195
196    if (subFinal != null)
197    {
198      int finalLength = subFinal.length;
199
200      if (valueLength - finalLength < pos)
201      {
202        return false;
203      }
204
205      pos = valueLength - finalLength;
206      for (int i=0; i < finalLength; i++,pos++)
207      {
208        if (!subFinal[i].matchesRDN(dn.rdn(pos)))
209        {
210          return false;
211        }
212      }
213    }
214
215    return pos <= valueLength;
216  }
217
218  private boolean subMatch(DN dn, int pos, PatternRDN[] element, int length)
219  {
220    for (int i = 1; i < length; i++)
221    {
222      if (!element[i].matchesRDN(dn.rdn(pos + i)))
223      {
224        return false;
225      }
226    }
227    return true;
228  }
229
230  /**
231   * Create a new DN pattern matcher to match a suffix.
232   * @param pattern The suffix pattern string.
233   * @throws org.opends.server.types.DirectoryException If the pattern string
234   * is not valid.
235   * @return A new DN pattern matcher.
236   */
237  public static PatternDN decodeSuffix(String pattern) throws DirectoryException
238  {
239    // Parse the user supplied pattern.
240    PatternDN patternDN = decode(pattern);
241
242    // Adjust the pattern so that it matches any DN ending with the pattern.
243    if (patternDN.equality != null)
244    {
245      // The pattern contained no Multiple-Whole-RDN wildcards,
246      // so we just convert the whole thing into a final fragment.
247      patternDN.subInitial = null;
248      patternDN.subFinal = patternDN.equality;
249      patternDN.subAnyElements = null;
250      patternDN.equality = null;
251    }
252    else if (patternDN.subInitial != null)
253    {
254      // The pattern had an initial fragment so we need to convert that into
255      // the head of the list of any elements.
256      patternDN.subAnyElements.add(0, patternDN.subInitial);
257      patternDN.subInitial = null;
258    }
259    patternDN.isSuffix = true;
260    return patternDN;
261  }
262
263  /**
264   * Create a new DN pattern matcher from a pattern string.
265   * @param dnString The DN pattern string.
266   * @throws org.opends.server.types.DirectoryException If the pattern string
267   * is not valid.
268   * @return A new DN pattern matcher.
269   */
270  public static PatternDN decode(String dnString) throws DirectoryException
271  {
272    List<PatternRDN> rdnComponents = new ArrayList<>();
273    List<Integer> doubleWildPos = new ArrayList<>();
274
275    // A null or empty DN is acceptable.
276    if (dnString == null)
277    {
278      return new PatternDN();
279    }
280
281    int length = dnString.length();
282    if (length == 0
283        // Special pattern "" to express rootDSE aka empty DN
284        || "\"\"".equals(dnString))
285    {
286      return new PatternDN();
287    }
288
289    // Iterate through the DN string.  The first thing to do is to get
290    // rid of any leading spaces.
291    int pos = 0;
292    char c = dnString.charAt(pos);
293    while (c == ' ')
294    {
295      pos++;
296      if (pos == length)
297      {
298        // This means that the DN was completely comprised of spaces
299        // and therefore should be considered the same as a null or empty DN.
300        return new PatternDN();
301      }
302      c = dnString.charAt(pos);
303    }
304
305    // We know that it's not an empty DN, so we can do the real
306    // processing. Create a loop and iterate through all the RDN components.
307    rdnLoop:
308    while (true)
309    {
310      int attributePos = pos;
311      StringBuilder attributeName = new StringBuilder();
312      pos = parseAttributePattern(dnString, pos, attributeName);
313      String name            = attributeName.toString();
314
315
316      // Make sure that we're not at the end of the DN string because
317      // that would be invalid.
318      if (pos >= length)
319      {
320        if (name.equals("*"))
321        {
322          rdnComponents.add(new PatternRDN(name, null, dnString));
323          break;
324        }
325        else if (name.equals("**"))
326        {
327          doubleWildPos.add(rdnComponents.size());
328          break;
329        }
330        else
331        {
332          pos = attributePos - 1;
333          name = "*";
334          c = '=';
335        }
336      }
337      else
338      {
339        // Skip over any spaces between the attribute name and its
340        // value.
341        c = dnString.charAt(pos);
342        while (c == ' ')
343        {
344          pos++;
345          if (pos >= length)
346          {
347            if (name.equals("*"))
348            {
349              rdnComponents.add(new PatternRDN(name, null, dnString));
350              break rdnLoop;
351            }
352            else if (name.equals("**"))
353            {
354              doubleWildPos.add(rdnComponents.size());
355              break rdnLoop;
356            }
357            else
358            {
359              pos = attributePos - 1;
360              name = "*";
361              c = '=';
362            }
363          }
364          else
365          {
366            c = dnString.charAt(pos);
367          }
368        }
369      }
370
371
372      if (c == '=')
373      {
374        pos++;
375      }
376      else if (c == ',' || c == ';')
377      {
378        if (name.equals("*"))
379        {
380          rdnComponents.add(new PatternRDN(name, null, dnString));
381          pos++;
382          continue;
383        }
384        else if (name.equals("**"))
385        {
386          doubleWildPos.add(rdnComponents.size());
387          pos++;
388          continue;
389        }
390        else
391        {
392          pos = attributePos;
393          name = "*";
394        }
395      }
396      else
397      {
398        throw new DirectoryException(ResultCode.INVALID_DN_SYNTAX,
399            ERR_ATTR_SYNTAX_DN_NO_EQUAL.get(dnString, attributeName, c));
400      }
401
402      // Skip over any spaces after the equal sign.
403      while (pos < length && dnString.charAt(pos) == ' ')
404      {
405        pos++;
406      }
407
408      // If we are at the end of the DN string, then that must mean
409      // that the attribute value was empty.  This will probably never
410      // happen in a real-world environment, but technically isn't
411      // illegal.  If it does happen, then go ahead and create the
412      // RDN component and return the DN.
413      if (pos >= length)
414      {
415        List<ByteString> valuePattern = newArrayList(ByteString.empty());
416        rdnComponents.add(new PatternRDN(name, valuePattern, dnString));
417        break;
418      }
419
420      // Parse the value for this RDN component.
421      List<ByteString> parsedValue = new ArrayList<>();
422      pos = parseValuePattern(dnString, pos, parsedValue);
423
424      // Create the new RDN with the provided information.
425      PatternRDN rdn = new PatternRDN(name, parsedValue, dnString);
426
427      // Skip over any spaces that might be after the attribute value.
428      while (pos < length && ((c = dnString.charAt(pos)) == ' '))
429      {
430        pos++;
431      }
432
433      // Most likely, we will be at either the end of the RDN
434      // component or the end of the DN. If so, then handle that appropriately.
435      if (pos >= length)
436      {
437        // We're at the end of the DN string and should have a valid DN so return it.
438        rdnComponents.add(rdn);
439        break;
440      }
441      else if (c == ',' || c == ';')
442      {
443        // We're at the end of the RDN component, so add it to the list,
444        // skip over the comma/semicolon, and start on the next component.
445        rdnComponents.add(rdn);
446        pos++;
447        continue;
448      }
449      else if (c != '+')
450      {
451        // This should not happen.  At any rate, it's an illegal
452        // character, so throw an exception.
453        LocalizableMessage message = ERR_ATTR_SYNTAX_DN_INVALID_CHAR.get(dnString, c, pos);
454        throw new DirectoryException(ResultCode.INVALID_DN_SYNTAX, message);
455      }
456
457      // If we have gotten here, then this must be a multi-valued RDN.
458      // In that case, parse the remaining attribute/value pairs and
459      // add them to the RDN that we've already created.
460      while (true)
461      {
462        // Skip over the plus sign and any spaces that may follow it
463        // before the next attribute name.
464        pos++;
465        while (pos < length && dnString.charAt(pos) == ' ')
466        {
467          pos++;
468        }
469
470        // Parse the attribute name from the DN string.
471        attributeName = new StringBuilder();
472        pos = parseAttributePattern(dnString, pos, attributeName);
473
474        // Make sure that we're not at the end of the DN string
475        // because that would be invalid.
476        if (pos >= length)
477        {
478          throw new DirectoryException(ResultCode.INVALID_DN_SYNTAX,
479              ERR_ATTR_SYNTAX_DN_END_WITH_ATTR_NAME.get(dnString, attributeName));
480        }
481
482        name = attributeName.toString();
483
484        // Skip over any spaces between the attribute name and its
485        // value.
486        c = dnString.charAt(pos);
487        while (c == ' ')
488        {
489          pos++;
490          if (pos >= length)
491          {
492            // This means that we hit the end of the value before
493            // finding a '='.  This is illegal because there is no
494            // attribute-value separator.
495            throw new DirectoryException(ResultCode.INVALID_DN_SYNTAX,
496                ERR_ATTR_SYNTAX_DN_END_WITH_ATTR_NAME.get(dnString, name));
497          }
498          c = dnString.charAt(pos);
499        }
500
501        // The next character must be an equal sign.  If it is not,
502        // then that's an error.
503        if (c == '=')
504        {
505          pos++;
506        }
507        else
508        {
509          LocalizableMessage message = ERR_ATTR_SYNTAX_DN_NO_EQUAL.get(dnString, name, c);
510          throw new DirectoryException(ResultCode.INVALID_DN_SYNTAX, message);
511        }
512
513        // Skip over any spaces after the equal sign.
514        while (pos < length && ((c = dnString.charAt(pos)) == ' '))
515        {
516          pos++;
517        }
518
519        // If we are at the end of the DN string, then that must mean
520        // that the attribute value was empty.  This will probably
521        // never happen in a real-world environment, but technically
522        // isn't illegal.  If it does happen, then go ahead and create
523        // the RDN component and return the DN.
524        if (pos >= length)
525        {
526          List<ByteString> valuePattern = newArrayList(ByteString.empty());
527          rdn.addValue(name, valuePattern, dnString);
528          rdnComponents.add(rdn);
529          break;
530        }
531
532        // Parse the value for this RDN component.
533        parsedValue = new ArrayList<>();
534        pos = parseValuePattern(dnString, pos, parsedValue);
535
536        // Create the new RDN with the provided information.
537        rdn.addValue(name, parsedValue, dnString);
538
539        // Skip over any spaces that might be after the attribute value.
540        while (pos < length && ((c = dnString.charAt(pos)) == ' '))
541        {
542          pos++;
543        }
544
545        // Most likely, we will be at either the end of the RDN
546        // component or the end of the DN.  If so, then handle that appropriately.
547        if (pos >= length)
548        {
549          // We're at the end of the DN string and should have a valid
550          // DN so return it.
551          rdnComponents.add(rdn);
552          break;
553        }
554        else if (c == ',' || c == ';')
555        {
556          // We're at the end of the RDN component, so add it to the
557          // list, skip over the comma/semicolon, and start on the next component.
558          rdnComponents.add(rdn);
559          pos++;
560          break;
561        }
562        else if (c != '+')
563        {
564          // This should not happen.  At any rate, it's an illegal
565          // character, so throw an exception.
566          LocalizableMessage message =
567              ERR_ATTR_SYNTAX_DN_INVALID_CHAR.get(dnString, c, pos);
568          throw new DirectoryException(ResultCode.INVALID_DN_SYNTAX, message);
569        }
570      }
571    }
572
573    if (doubleWildPos.isEmpty())
574    {
575      return new PatternDN(rdnComponents.toArray(new PatternRDN[rdnComponents.size()]));
576    }
577
578    PatternRDN[] subInitial = null;
579    PatternRDN[] subFinal = null;
580    List<PatternRDN[]> subAnyElements = new ArrayList<>();
581
582    int i = 0;
583    int numComponents = rdnComponents.size();
584
585    int to = doubleWildPos.get(i);
586    if (to != 0)
587    {
588      // Initial piece.
589      subInitial = new PatternRDN[to];
590      subInitial = rdnComponents.subList(0, to).toArray(subInitial);
591    }
592
593    int from;
594    for (; i < doubleWildPos.size() - 1; i++)
595    {
596      from = doubleWildPos.get(i);
597      to = doubleWildPos.get(i + 1);
598      PatternRDN[] subAny = new PatternRDN[to - from];
599      subAny = rdnComponents.subList(from, to).toArray(subAny);
600      subAnyElements.add(subAny);
601    }
602
603    if (i < doubleWildPos.size())
604    {
605      from = doubleWildPos.get(i);
606      if (from != numComponents)
607      {
608        // Final piece.
609        subFinal = new PatternRDN[numComponents - from];
610        subFinal = rdnComponents.subList(from, numComponents).toArray(subFinal);
611      }
612    }
613
614    return new PatternDN(subInitial, subAnyElements, subFinal);
615  }
616
617  /**
618   * Parses an attribute name pattern from the provided DN pattern string
619   * starting at the specified location.
620   *
621   * @param  dnString         The DN pattern string to be parsed.
622   * @param  pos              The position at which to start parsing
623   *                          the attribute name pattern.
624   * @param  attributeName    The buffer to which to append the parsed
625   *                          attribute name pattern.
626   *
627   * @return  The position of the first character that is not part of
628   *          the attribute name pattern.
629   *
630   * @throws  DirectoryException  If it was not possible to parse a
631   *                              valid attribute name pattern from the
632   *                              provided DN pattern string.
633   */
634  private static int parseAttributePattern(String dnString, int pos,
635                                   StringBuilder attributeName)
636          throws DirectoryException
637  {
638    int length = dnString.length();
639
640    // Skip over any leading spaces.
641    if (pos < length)
642    {
643      while (dnString.charAt(pos) == ' ')
644      {
645        pos++;
646        if (pos == length)
647        {
648          // This means that the remainder of the DN was completely
649          // comprised of spaces.  If we have gotten here, then we
650          // know that there is at least one RDN component, and
651          // therefore the last non-space character of the DN must
652          // have been a comma. This is not acceptable.
653          LocalizableMessage message = ERR_ATTR_SYNTAX_DN_END_WITH_COMMA.get(dnString);
654          throw new DirectoryException(ResultCode.INVALID_DN_SYNTAX, message);
655        }
656      }
657    }
658
659    // Next, we should find the attribute name for this RDN component.
660    boolean       checkForOID   = false;
661    boolean       endOfName     = false;
662    while (pos < length)
663    {
664      // To make the switch more efficient, we'll include all ASCII
665      // characters in the range of allowed values and then reject the
666      // ones that aren't allowed.
667      char c = dnString.charAt(pos);
668      switch (c)
669      {
670        case ' ':
671          // This should denote the end of the attribute name.
672          endOfName = true;
673          break;
674
675        case '!':
676        case '"':
677        case '#':
678        case '$':
679        case '%':
680        case '&':
681        case '\'':
682        case '(':
683        case ')':
684          // None of these are allowed in an attribute name or any
685          // character immediately following it.
686          throw illegalCharacter(dnString, pos, c);
687
688        case '*':
689          // Wildcard character.
690          attributeName.append(c);
691          break;
692
693        case '+':
694          throw illegalCharacter(dnString, pos, c);
695
696        case ',':
697          // This should denote the end of the attribute name.
698          endOfName = true;
699          break;
700
701        case '-':
702          // This will be allowed as long as it isn't the first
703          // character in the attribute name.
704          if (attributeName.length() == 0)
705          {
706            LocalizableMessage message = ERR_ATTR_SYNTAX_DN_ATTR_ILLEGAL_INITIAL_DASH.get(dnString);
707            throw new DirectoryException(ResultCode.INVALID_DN_SYNTAX, message);
708          }
709          attributeName.append(c);
710          break;
711
712        case '.':
713          // The period could be allowed if the attribute name is
714          // actually expressed as an OID.  We'll accept it for now,
715          // but make sure to check it later.
716          attributeName.append(c);
717          checkForOID = true;
718          break;
719
720        case '/':
721          throw illegalCharacter(dnString, pos, c);
722
723        case '0':
724        case '1':
725        case '2':
726        case '3':
727        case '4':
728        case '5':
729        case '6':
730        case '7':
731        case '8':
732        case '9':
733          // Digits are always allowed if they are not the first
734          // character. However, they may be allowed if they are the
735          // first character if the valid is an OID or if the
736          // attribute name exceptions option is enabled.  Therefore,
737          // we'll accept it now and check it later.
738          attributeName.append(c);
739          break;
740
741        case ':':
742          throw illegalCharacter(dnString, pos, c);
743
744        case ';': // NOTE:  attribute options are not allowed in a DN.
745          // This should denote the end of the attribute name.
746          endOfName = true;
747          break;
748
749        case '<':
750          throw illegalCharacter(dnString, pos, c);
751
752        case '=':
753          // This should denote the end of the attribute name.
754          endOfName = true;
755          break;
756
757        case '>':
758        case '?':
759        case '@':
760          throw illegalCharacter(dnString, pos, c);
761
762        case 'A':
763        case 'B':
764        case 'C':
765        case 'D':
766        case 'E':
767        case 'F':
768        case 'G':
769        case 'H':
770        case 'I':
771        case 'J':
772        case 'K':
773        case 'L':
774        case 'M':
775        case 'N':
776        case 'O':
777        case 'P':
778        case 'Q':
779        case 'R':
780        case 'S':
781        case 'T':
782        case 'U':
783        case 'V':
784        case 'W':
785        case 'X':
786        case 'Y':
787        case 'Z':
788          // These will always be allowed.
789          attributeName.append(c);
790          break;
791
792        case '[':
793        case '\\':
794        case ']':
795        case '^':
796          throw illegalCharacter(dnString, pos, c);
797
798        case '_':
799          attributeName.append(c);
800          break;
801
802        case '`':
803          throw illegalCharacter(dnString, pos, c);
804
805        case 'a':
806        case 'b':
807        case 'c':
808        case 'd':
809        case 'e':
810        case 'f':
811        case 'g':
812        case 'h':
813        case 'i':
814        case 'j':
815        case 'k':
816        case 'l':
817        case 'm':
818        case 'n':
819        case 'o':
820        case 'p':
821        case 'q':
822        case 'r':
823        case 's':
824        case 't':
825        case 'u':
826        case 'v':
827        case 'w':
828        case 'x':
829        case 'y':
830        case 'z':
831          // These will always be allowed.
832          attributeName.append(c);
833          break;
834
835        default:
836          // This is not allowed in an attribute name or any character
837          // immediately following it.
838          throw illegalCharacter(dnString, pos, c);
839      }
840
841      if (endOfName)
842      {
843        break;
844      }
845
846      pos++;
847    }
848
849    // We should now have the full attribute name.  However, we may
850    // still need to perform some validation, particularly if the
851    // name contains a period or starts with a digit.  It must also
852    // have at least one character.
853    if (attributeName.length() == 0)
854    {
855      LocalizableMessage message = ERR_ATTR_SYNTAX_DN_ATTR_NO_NAME.get(dnString);
856      throw new DirectoryException(ResultCode.INVALID_DN_SYNTAX, message);
857    }
858    else if (checkForOID)
859    {
860      boolean validOID = true;
861
862      int namePos = 0;
863      int nameLength = attributeName.length();
864      char ch0 = attributeName.charAt(0);
865      if (ch0 == 'o' || ch0 == 'O')
866      {
867        if (nameLength <= 4)
868        {
869          validOID = false;
870        }
871        else
872        {
873          char ch1 = attributeName.charAt(1);
874          char ch2 = attributeName.charAt(2);
875          if ((ch1 == 'i' || ch1 == 'I')
876              && (ch2 == 'd' || ch2 == 'D')
877              && attributeName.charAt(3) == '.')
878          {
879            attributeName.delete(0, 4);
880            nameLength -= 4;
881          }
882          else
883          {
884            validOID = false;
885          }
886        }
887      }
888
889      while (validOID && namePos < nameLength)
890      {
891        char ch = attributeName.charAt(namePos++);
892        if (isDigit(ch))
893        {
894          while (validOID && namePos < nameLength &&
895                 isDigit(attributeName.charAt(namePos)))
896          {
897            namePos++;
898          }
899
900          if (namePos < nameLength &&
901              attributeName.charAt(namePos) != '.')
902          {
903            validOID = false;
904          }
905        }
906        else if (ch == '.')
907        {
908          if (namePos == 1 ||
909              attributeName.charAt(namePos-2) == '.')
910          {
911            validOID = false;
912          }
913        }
914        else
915        {
916          validOID = false;
917        }
918      }
919
920      if (validOID && attributeName.charAt(nameLength-1) == '.')
921      {
922        validOID = false;
923      }
924
925      if (! validOID)
926      {
927        throw new DirectoryException(ResultCode.INVALID_DN_SYNTAX,
928            ERR_ATTR_SYNTAX_DN_ATTR_ILLEGAL_PERIOD.get(dnString, attributeName));
929      }
930    }
931
932    return pos;
933  }
934
935  private static DirectoryException illegalCharacter(String dnString, int pos, char c)
936  {
937    return new DirectoryException(ResultCode.INVALID_DN_SYNTAX,
938        ERR_ATTR_SYNTAX_DN_ATTR_ILLEGAL_CHAR.get(dnString, c, pos));
939  }
940
941  /**
942   * Parses the attribute value pattern from the provided DN pattern
943   * string starting at the specified location.  The value is split up
944   * according to the wildcard locations, and the fragments are inserted
945   * into the provided list.
946   *
947   * @param  dnString        The DN pattern string to be parsed.
948   * @param  pos             The position of the first character in
949   *                         the attribute value pattern to parse.
950   * @param  attributeValues The list whose elements should be set to
951   *                         the parsed attribute value fragments when
952   *                         this method completes successfully.
953   *
954   * @return  The position of the first character that is not part of
955   *          the attribute value.
956   *
957   * @throws  DirectoryException  If it was not possible to parse a
958   *                              valid attribute value pattern from the
959   *                              provided DN string.
960   */
961  private static int parseValuePattern(String dnString, int pos,
962                                       List<ByteString> attributeValues)
963          throws DirectoryException
964  {
965    // All leading spaces have already been stripped so we can start
966    // reading the value.  However, it may be empty so check for that.
967    int length = dnString.length();
968    if (pos >= length)
969    {
970      return pos;
971    }
972
973    // Look at the first character.  If it is an octothorpe (#), then
974    // that means that the value should be a hex string.
975    char c = dnString.charAt(pos++);
976    if (c == '#')
977    {
978      // The first two characters must be hex characters.
979      StringBuilder hexString = new StringBuilder();
980      if (pos+2 > length)
981      {
982        LocalizableMessage message = ERR_ATTR_SYNTAX_DN_HEX_VALUE_TOO_SHORT.get(dnString);
983        throw new DirectoryException(ResultCode.INVALID_DN_SYNTAX, message);
984      }
985
986      for (int i=0; i < 2; i++)
987      {
988        c = dnString.charAt(pos++);
989        if (isHexDigit(c))
990        {
991          hexString.append(c);
992        }
993        else
994        {
995          LocalizableMessage message = ERR_ATTR_SYNTAX_DN_INVALID_HEX_DIGIT.get(dnString, c);
996          throw new DirectoryException(ResultCode.INVALID_DN_SYNTAX, message);
997        }
998      }
999
1000      // The rest of the value must be a multiple of two hex
1001      // characters.  The end of the value may be designated by the
1002      // end of the DN, a comma or semicolon, or a space.
1003      while (pos < length)
1004      {
1005        c = dnString.charAt(pos++);
1006        if (isHexDigit(c))
1007        {
1008          hexString.append(c);
1009
1010          if (pos < length)
1011          {
1012            c = dnString.charAt(pos++);
1013            if (isHexDigit(c))
1014            {
1015              hexString.append(c);
1016            }
1017            else
1018            {
1019              LocalizableMessage message = ERR_ATTR_SYNTAX_DN_INVALID_HEX_DIGIT.get(dnString, c);
1020              throw new DirectoryException(ResultCode.INVALID_DN_SYNTAX, message);
1021            }
1022          }
1023          else
1024          {
1025            LocalizableMessage message = ERR_ATTR_SYNTAX_DN_HEX_VALUE_TOO_SHORT.get(dnString);
1026            throw new DirectoryException(ResultCode.INVALID_DN_SYNTAX, message);
1027          }
1028        }
1029        else if (c == ' ' || c == ',' || c == ';')
1030        {
1031          // This denotes the end of the value.
1032          pos--;
1033          break;
1034        }
1035        else
1036        {
1037          LocalizableMessage message = ERR_ATTR_SYNTAX_DN_INVALID_HEX_DIGIT.get(dnString, c);
1038          throw new DirectoryException(ResultCode.INVALID_DN_SYNTAX, message);
1039        }
1040      }
1041
1042      // At this point, we should have a valid hex string.  Convert it
1043      // to a byte array and set that as the value of the provided
1044      // octet string.
1045      try
1046      {
1047        byte[] bytes = hexStringToByteArray(hexString.toString());
1048        attributeValues.add(ByteString.wrap(bytes));
1049        return pos;
1050      }
1051      catch (Exception e)
1052      {
1053        logger.traceException(e);
1054        throw new DirectoryException(ResultCode.INVALID_DN_SYNTAX,
1055            ERR_ATTR_SYNTAX_DN_ATTR_VALUE_DECODE_FAILURE.get(dnString, e));
1056      }
1057    }
1058
1059    // If the first character is a quotation mark, then the value
1060    // should continue until the corresponding closing quotation mark.
1061    else if (c == '"')
1062    {
1063      // Keep reading until we find an unescaped closing quotation mark.
1064      boolean escaped = false;
1065      StringBuilder valueString = new StringBuilder();
1066      while (true)
1067      {
1068        if (pos >= length)
1069        {
1070          // We hit the end of the DN before the closing quote.
1071          // That's an error.
1072          LocalizableMessage message = ERR_ATTR_SYNTAX_DN_UNMATCHED_QUOTE.get(dnString);
1073          throw new DirectoryException(ResultCode.INVALID_DN_SYNTAX, message);
1074        }
1075
1076        c = dnString.charAt(pos++);
1077        if (escaped)
1078        {
1079          // The previous character was an escape, so we'll take this
1080          // one no matter what.
1081          valueString.append(c);
1082          escaped = false;
1083        }
1084        else if (c == '\\')
1085        {
1086          // The next character is escaped.  Set a flag to denote
1087          // this, but don't include the backslash.
1088          escaped = true;
1089        }
1090        else if (c == '"')
1091        {
1092          // This is the end of the value.
1093          break;
1094        }
1095        else
1096        {
1097          // This is just a regular character that should be in the
1098          // value.
1099          valueString.append(c);
1100        }
1101      }
1102
1103      attributeValues.add(ByteString.valueOfUtf8(valueString));
1104      return pos;
1105    }
1106
1107    // Otherwise, use general parsing to find the end of the value.
1108    else
1109    {
1110      boolean escaped;
1111      StringBuilder valueString = new StringBuilder();
1112      StringBuilder hexChars    = new StringBuilder();
1113
1114      if (c == '\\')
1115      {
1116        escaped = true;
1117      }
1118      else if (c == '*')
1119      {
1120        escaped = false;
1121        attributeValues.add(ByteString.valueOfUtf8(valueString));
1122      }
1123      else
1124      {
1125        escaped = false;
1126        valueString.append(c);
1127      }
1128
1129      // Keep reading until we find an unescaped comma or plus sign or the end of the DN.
1130      while (true)
1131      {
1132        if (pos >= length)
1133        {
1134          // This is the end of the DN and therefore the end of the value.
1135          // If there are any hex characters, then we need to deal with them accordingly.
1136          appendHexChars(dnString, valueString, hexChars);
1137          break;
1138        }
1139
1140        c = dnString.charAt(pos++);
1141        if (escaped)
1142        {
1143          // The previous character was an escape, so we'll take this one.
1144          // However, this could be a hex digit, and if that's
1145          // the case then the escape would actually be in front of
1146          // two hex digits that should be treated as a special character.
1147          if (isHexDigit(c))
1148          {
1149            // It is a hexadecimal digit, so the next digit must be one too.
1150            // However, this could be just one in a series of escaped hex pairs
1151            // that is used in a string containing one or more multi-byte UTF-8
1152            // characters so we can't just treat this byte in isolation.
1153            // Collect all the bytes together and make sure to take care of
1154            // these hex bytes before appending anything else to the value.
1155            if (pos >= length)
1156            {
1157              LocalizableMessage message = ERR_ATTR_SYNTAX_DN_ESCAPED_HEX_VALUE_INVALID.get(dnString);
1158              throw new DirectoryException(ResultCode.INVALID_DN_SYNTAX, message);
1159            }
1160            char c2 = dnString.charAt(pos++);
1161            if (!isHexDigit(c2))
1162            {
1163              LocalizableMessage message = ERR_ATTR_SYNTAX_DN_ESCAPED_HEX_VALUE_INVALID.get(dnString);
1164              throw new DirectoryException(ResultCode.INVALID_DN_SYNTAX, message);
1165            }
1166            hexChars.append(c);
1167            hexChars.append(c2);
1168          }
1169          else
1170          {
1171            appendHexChars(dnString, valueString, hexChars);
1172            valueString.append(c);
1173          }
1174
1175          escaped = false;
1176        }
1177        else if (c == '\\')
1178        {
1179          escaped = true;
1180        }
1181        else if (c == ',' || c == ';')
1182        {
1183          appendHexChars(dnString, valueString, hexChars);
1184          pos--;
1185          break;
1186        }
1187        else if (c == '+')
1188        {
1189          appendHexChars(dnString, valueString, hexChars);
1190          pos--;
1191          break;
1192        }
1193        else if (c == '*')
1194        {
1195          appendHexChars(dnString, valueString, hexChars);
1196          if (valueString.length() == 0)
1197          {
1198            LocalizableMessage message =
1199                WARN_PATTERN_DN_CONSECUTIVE_WILDCARDS_IN_VALUE.get(dnString);
1200            throw new DirectoryException(ResultCode.INVALID_DN_SYNTAX, message);
1201          }
1202          attributeValues.add(ByteString.valueOfUtf8(valueString));
1203          valueString = new StringBuilder();
1204          hexChars = new StringBuilder();
1205        }
1206        else
1207        {
1208          appendHexChars(dnString, valueString, hexChars);
1209          valueString.append(c);
1210        }
1211      }
1212
1213      // Strip off any unescaped spaces that may be at the end of the
1214      // value.
1215      if (pos > 2 && dnString.charAt(pos-1) == ' ' &&
1216           dnString.charAt(pos-2) != '\\')
1217      {
1218        int lastPos = valueString.length() - 1;
1219        while (lastPos > 0)
1220        {
1221          if (valueString.charAt(lastPos) != ' ')
1222          {
1223            break;
1224          }
1225          valueString.delete(lastPos, lastPos + 1);
1226          lastPos--;
1227        }
1228      }
1229
1230      attributeValues.add(ByteString.valueOfUtf8(valueString));
1231      return pos;
1232    }
1233  }
1234
1235  /**
1236   * Decodes a hexadecimal string from the provided
1237   * <CODE>hexChars</CODE> buffer, converts it to a byte array, and
1238   * then converts that to a UTF-8 string.  The resulting UTF-8 string
1239   * will be appended to the provided <CODE>valueString</CODE> buffer,
1240   * and the <CODE>hexChars</CODE> buffer will be cleared.
1241   *
1242   * @param  dnString     The DN string that is being decoded.
1243   * @param  valueString  The buffer containing the value to which the
1244   *                      decoded string should be appended.
1245   * @param  hexChars     The buffer containing the hexadecimal
1246   *                      characters to decode to a UTF-8 string.
1247   *
1248   * @throws  DirectoryException  If any problem occurs during the
1249   *                              decoding process.
1250   */
1251  private static void appendHexChars(String dnString,
1252                                     StringBuilder valueString,
1253                                     StringBuilder hexChars)
1254          throws DirectoryException
1255  {
1256    try
1257    {
1258      byte[] hexBytes = hexStringToByteArray(hexChars.toString());
1259      valueString.append(new String(hexBytes, "UTF-8"));
1260      hexChars.delete(0, hexChars.length());
1261    }
1262    catch (Exception e)
1263    {
1264      logger.traceException(e);
1265      throw new DirectoryException(ResultCode.INVALID_DN_SYNTAX,
1266          ERR_ATTR_SYNTAX_DN_ATTR_VALUE_DECODE_FAILURE.get(dnString, e));
1267    }
1268  }
1269
1270  @Override
1271  public String toString()
1272  {
1273    if (this.equality != null)
1274    {
1275      return getClass().getSimpleName() + "(equality=" + Arrays.toString(equality) + ")";
1276    }
1277    StringBuilder sb = new StringBuilder(getClass().getSimpleName()).append("(substring:");
1278    if (subInitial!=null) {
1279      sb.append(" subInitial=").append(Arrays.toString(subInitial));
1280    }
1281    sb.append(", subAnyElements=[");
1282    final Iterator<PatternRDN[]> iterator = subAnyElements.iterator();
1283    if (iterator.hasNext()) {
1284        sb.append(Arrays.toString(iterator.next()));
1285
1286        while (iterator.hasNext()) {
1287            sb.append(", ");
1288            sb.append(Arrays.toString(iterator.next()));
1289        }
1290    }
1291    sb.append("]");
1292    sb.append(", subFinal=").append(Arrays.toString(subFinal)).append(")");
1293    return sb.toString();
1294  }
1295}