org.spearce.jgit/src/org/spearce/jgit/fnmatch/FileNameMatcher.java

   1 /*
   2  * Copyright (C) 2008, Florian Köberle <florianskarten@web.de>
   3  *
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or
   7  * without modification, are permitted provided that the following
   8  * conditions are met:
   9  *
  10  * - Redistributions of source code must retain the above copyright
  11  *   notice, this list of conditions and the following disclaimer.
  12  *
  13  * - Redistributions in binary form must reproduce the above
  14  *   copyright notice, this list of conditions and the following
  15  *   disclaimer in the documentation and/or other materials provided
  16  *   with the distribution.
  17  *
  18  * - Neither the name of the Git Development Community nor the
  19  *   names of its contributors may be used to endorse or promote
  20  *   products derived from this software without specific prior
  21  *   written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  24  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  25  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  26  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  28  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  29  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  30  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  31  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  32  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  33  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  34  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  35  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  36  */
  37
  38 package org.spearce.jgit.fnmatch;
  39
  40 import java.util.ArrayList;
  41 import java.util.Collections;
  42 import java.util.List;
  43 import java.util.ListIterator;
  44 import java.util.regex.Matcher;
  45 import java.util.regex.Pattern;
  46
  47 import org.spearce.jgit.errors.InvalidPatternException;
  48 import org.spearce.jgit.errors.NoClosingBracketException;
  49
  50 /**
  51  * This class can be used to match filenames against fnmatch like patterns. It
  52  * is not thread save.
  53  * <p>
  54  * Supported are the wildcard characters * and ? and groups with:
  55  * <ul>
  56  * <li> characters e.g. [abc]</li>
  57  * <li> ranges e.g. [a-z]</li>
  58  * <li> the following character classes
  59  * <ul>
  60  * <li>[:alnum:]</li>
  61  * <li>[:alpha:]</li>
  62  * <li>[:blank:]</li>
  63  * <li>[:cntrl:]</li>
  64  * <li>[:digit:]</li>
  65  * <li>[:graph:]</li>
  66  * <li>[:lower:]</li>
  67  * <li>[:print:]</li>
  68  * <li>[:punct:]</li>
  69  * <li>[:space:]</li>
  70  * <li>[:upper:]</li>
  71  * <li>[:word:]</li>
  72  * <li>[:xdigit:]</li>
  73  * </ul>
  74  * e. g. [[:xdigit:]] </li>
  75  * </ul>
  76  * </p>
  77  */
  78 public class FileNameMatcher {
  79         static final List<Head> EMPTY_HEAD_LIST = Collections.emptyList();
  80
  81         private static final Pattern characterClassStartPattern = Pattern
  82                         .compile("\\[[.:=]");
  83
  84         private List<Head> headsStartValue;
  85
  86         private List<Head> heads;
  87
  88         /**
  89          * {{@link #extendStringToMatchByOneCharacter(char)} needs a list for the
  90          * new heads, allocating a new array would be bad for the performance, as
  91          * the method gets called very often.
  92          *
  93          */
  94         private List<Head> listForLocalUseage;
  95
  96         /**
  97          *
  98          * @param headsStartValue
  99          *            must be a list which will never be modified.
 100          */
 101         private FileNameMatcher(final List<Head> headsStartValue) {
 102                 this(headsStartValue, headsStartValue);
 103         }
 104
 105         /**
 106          *
 107          * @param headsStartValue
 108          *            must be a list which will never be modified.
 109          * @param heads
 110          *            a list which will be cloned and then used as current head
 111          *            list.
 112          */
 113         private FileNameMatcher(final List<Head> headsStartValue,
 114                         final List<Head> heads) {
 115                 this.headsStartValue = headsStartValue;
 116                 this.heads = new ArrayList<Head>(heads.size());
 117                 this.heads.addAll(heads);
 118                 this.listForLocalUseage = new ArrayList<Head>(heads.size());
 119         }
 120
 121         /**
 122          * @param patternString
 123          *            must contain a pattern which fnmatch would accept.
 124          * @param invalidWildgetCharacter
 125          *            if this parameter isn't null then this character will not
 126          *            match at wildcards(* and ? are wildcards).
 127          * @throws InvalidPatternException
 128          *             if the patternString contains a invalid fnmatch pattern.
 129          */
 130         public FileNameMatcher(final String patternString,
 131                         final Character invalidWildgetCharacter)
 132                         throws InvalidPatternException {
 133                 this(createHeadsStartValues(patternString, invalidWildgetCharacter));
 134         }
 135
 136         /**
 137          * A Copy Constructor which creates a new {@link FileNameMatcher} with the
 138          * same state and reset point like <code>other</code>.
 139          *
 140          * @param other
 141          *            another {@link FileNameMatcher} instance.
 142          */
 143         public FileNameMatcher(FileNameMatcher other) {
 144                 this(other.headsStartValue, other.heads);
 145         }
 146
 147         private static List<Head> createHeadsStartValues(
 148                         final String patternString, final Character invalidWildgetCharacter)
 149                         throws InvalidPatternException {
 150
 151                 final List<AbstractHead> allHeads = parseHeads(patternString,
 152                                 invalidWildgetCharacter);
 153
 154                 List<Head> nextHeadsSuggestion = new ArrayList<Head>(2);
 155                 nextHeadsSuggestion.add(LastHead.INSTANCE);
 156                 for (int i = allHeads.size() - 1; i >= 0; i--) {
 157                         final AbstractHead head = allHeads.get(i);
 158
 159                         // explanation:
 160                         // a and * of the pattern "a*b"
 161                         // need *b as newHeads
 162                         // that's why * extends the list for it self and it's left neighbor.
 163                         if (head.isStar()) {
 164                                 nextHeadsSuggestion.add(head);
 165                                 head.setNewHeads(nextHeadsSuggestion);
 166                         } else {
 167                                 head.setNewHeads(nextHeadsSuggestion);
 168                                 nextHeadsSuggestion = new ArrayList<Head>(2);
 169                                 nextHeadsSuggestion.add(head);
 170                         }
 171                 }
 172                 return nextHeadsSuggestion;
 173         }
 174
 175         private static int findGroupEnd(final int indexOfStartBracket,
 176                         final String pattern) throws InvalidPatternException {
 177                 int firstValidCharClassIndex = indexOfStartBracket + 1;
 178                 int firstValidEndBracketIndex = indexOfStartBracket + 2;
 179
 180                 if (indexOfStartBracket + 1 >= pattern.length())
 181                         throw new NoClosingBracketException(indexOfStartBracket, "[", "]",
 182                                         pattern);
 183
 184                 if (pattern.charAt(firstValidCharClassIndex) == '!') {
 185                         firstValidCharClassIndex++;
 186                         firstValidEndBracketIndex++;
 187                 }
 188
 189                 final Matcher charClassStartMatcher = characterClassStartPattern
 190                                 .matcher(pattern);
 191
 192                 int groupEnd = -1;
 193                 while (groupEnd == -1) {
 194
 195                         final int possibleGroupEnd = pattern.indexOf(']',
 196                                         firstValidEndBracketIndex);
 197                         if (possibleGroupEnd == -1)
 198                                 throw new NoClosingBracketException(indexOfStartBracket, "[",
 199                                                 "]", pattern);
 200
 201                         final boolean foundCharClass = charClassStartMatcher
 202                                         .find(firstValidCharClassIndex);
 203
 204                         if (foundCharClass
 205                                         && charClassStartMatcher.start() < possibleGroupEnd) {
 206
 207                                 final String classStart = charClassStartMatcher.group(0);
 208                                 final String classEnd = classStart.charAt(1) + "]";
 209
 210                                 final int classStartIndex = charClassStartMatcher.start();
 211                                 final int classEndIndex = pattern.indexOf(classEnd,
 212                                                 classStartIndex + 2);
 213
 214                                 if (classEndIndex == -1)
 215                                         throw new NoClosingBracketException(classStartIndex,
 216                                                         classStart, classEnd, pattern);
 217
 218                                 firstValidCharClassIndex = classEndIndex + 2;
 219                                 firstValidEndBracketIndex = firstValidCharClassIndex;
 220                         } else {
 221                                 groupEnd = possibleGroupEnd;
 222                         }
 223                 }
 224                 return groupEnd;
 225         }
 226
 227         private static List<AbstractHead> parseHeads(final String pattern,
 228                         final Character invalidWildgetCharacter)
 229                         throws InvalidPatternException {
 230
 231                 int currentIndex = 0;
 232                 List<AbstractHead> heads = new ArrayList<AbstractHead>();
 233                 while (currentIndex < pattern.length()) {
 234                         final int groupStart = pattern.indexOf('[', currentIndex);
 235                         if (groupStart == -1) {
 236                                 final String patternPart = pattern.substring(currentIndex);
 237                                 heads.addAll(createSimpleHeads(patternPart,
 238                                                 invalidWildgetCharacter));
 239                                 currentIndex = pattern.length();
 240                         } else {
 241                                 final String patternPart = pattern.substring(currentIndex,
 242                                                 groupStart);
 243                                 heads.addAll(createSimpleHeads(patternPart,
 244                                                 invalidWildgetCharacter));
 245
 246                                 final int groupEnd = findGroupEnd(groupStart, pattern);
 247                                 final String groupPart = pattern.substring(groupStart + 1,
 248                                                 groupEnd);
 249                                 heads.add(new GroupHead(groupPart, pattern));
 250                                 currentIndex = groupEnd + 1;
 251                         }
 252                 }
 253                 return heads;
 254         }
 255
 256         private static List<AbstractHead> createSimpleHeads(
 257                         final String patternPart, final Character invalidWildgetCharacter) {
 258                 final List<AbstractHead> heads = new ArrayList<AbstractHead>(
 259                                 patternPart.length());
 260                 for (int i = 0; i < patternPart.length(); i++) {
 261                         final char c = patternPart.charAt(i);
 262                         switch (c) {
 263                         case '*': {
 264                                 final AbstractHead head = createWildCardHead(
 265                                                 invalidWildgetCharacter, true);
 266                                 heads.add(head);
 267                                 break;
 268                         }
 269                         case '?': {
 270                                 final AbstractHead head = createWildCardHead(
 271                                                 invalidWildgetCharacter, false);
 272                                 heads.add(head);
 273                                 break;
 274                         }
 275                         default:
 276                                 final CharacterHead head = new CharacterHead(c);
 277                                 heads.add(head);
 278                         }
 279                 }
 280                 return heads;
 281         }
 282
 283         private static AbstractHead createWildCardHead(
 284                         final Character invalidWildgetCharacter, final boolean star) {
 285                 if (invalidWildgetCharacter != null)
 286                         return new RestrictedWildCardHead(invalidWildgetCharacter
 287                                         .charValue(), star);
 288                 else
 289                         return new WildCardHead(star);
 290         }
 291
 292         private void extendStringToMatchByOneCharacter(final char c) {
 293                 final List<Head> newHeads = listForLocalUseage;
 294                 newHeads.clear();
 295                 List<Head> lastAddedHeads = null;
 296                 for (int i = 0; i < heads.size(); i++) {
 297                         final Head head = heads.get(i);
 298                         final List<Head> headsToAdd = head.getNextHeads(c);
 299                         // Why the next performance optimization isn't wrong:
 300                         // Some times two heads return the very same list.
 301                         // We save future effort if we don't add these heads again.
 302                         // This is the case with the heads "a" and "*" of "a*b" which
 303                         // both can return the list ["*","b"]
 304                         if (headsToAdd != lastAddedHeads) {
 305                                 newHeads.addAll(headsToAdd);
 306                                 lastAddedHeads = headsToAdd;
 307                         }
 308                 }
 309                 listForLocalUseage = heads;
 310                 heads = newHeads;
 311         }
 312
 313         /**
 314          *
 315          * @param stringToMatch
 316          *            extends the string which is matched against the patterns of
 317          *            this class.
 318          */
 319         public void append(final String stringToMatch) {
 320                 for (int i = 0; i < stringToMatch.length(); i++) {
 321                         final char c = stringToMatch.charAt(i);
 322                         extendStringToMatchByOneCharacter(c);
 323                 }
 324         }
 325
 326         /**
 327          * Resets this matcher to it's state right after construction.
 328          */
 329         public void reset() {
 330                 heads.clear();
 331                 heads.addAll(headsStartValue);
 332         }
 333
 334         /**
 335          *
 336          * @return a {@link FileNameMatcher} instance which uses the same pattern
 337          *         like this matcher, but has the current state of this matcher as
 338          *         reset and start point.
 339          */
 340         public FileNameMatcher createMatcherForSuffix() {
 341                 final List<Head> copyOfHeads = new ArrayList<Head>(heads.size());
 342                 copyOfHeads.addAll(heads);
 343                 return new FileNameMatcher(copyOfHeads);
 344         }
 345
 346         /**
 347          *
 348          * @return true, if the string currently being matched does match.
 349          */
 350         public boolean isMatch() {
 351                 final ListIterator<Head> headIterator = heads
 352                                 .listIterator(heads.size());
 353                 while (headIterator.hasPrevious()) {
 354                         final Head head = headIterator.previous();
 355                         if (head == LastHead.INSTANCE) {
 356                                 return true;
 357                         }
 358                 }
 359                 return false;
 360         }
 361
 362         /**
 363          *
 364          * @return false, if the string being matched will not match when the string
 365          *         gets extended.
 366          */
 367         public boolean canAppendMatch() {
 368                 for (int i = 0; i < heads.size(); i++) {
 369                         if (heads.get(i) != LastHead.INSTANCE) {
 370                                 return true;
 371                         }
 372                 }
 373                 return false;
 374         }
 375 }