2 * Copyright (C) 2008, Florian Köberle <florianskarten@web.de>
6 * Redistribution and use in source and binary forms, with or
7 * without modification, are permitted provided that the following
10 * - Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
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.
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
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.
38 package org
.spearce
.jgit
.fnmatch
;
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
;
47 import org
.spearce
.jgit
.errors
.InvalidPatternException
;
48 import org
.spearce
.jgit
.errors
.NoClosingBracketException
;
51 * This class can be used to match filenames against fnmatch like patterns. It
54 * Supported are the wildcard characters * and ? and groups with:
56 * <li> characters e.g. [abc]</li>
57 * <li> ranges e.g. [a-z]</li>
58 * <li> the following character classes
74 * e. g. [[:xdigit:]] </li>
78 public class FileNameMatcher
{
79 static final List
<Head
> EMPTY_HEAD_LIST
= Collections
.emptyList();
81 private static final Pattern characterClassStartPattern
= Pattern
84 private List
<Head
> headsStartValue
;
86 private List
<Head
> heads
;
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.
94 private List
<Head
> listForLocalUseage
;
98 * @param headsStartValue
99 * must be a list which will never be modified.
101 private FileNameMatcher(final List
<Head
> headsStartValue
) {
102 this(headsStartValue
, headsStartValue
);
107 * @param headsStartValue
108 * must be a list which will never be modified.
110 * a list which will be cloned and then used as current head
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());
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.
130 public FileNameMatcher(final String patternString
,
131 final Character invalidWildgetCharacter
)
132 throws InvalidPatternException
{
133 this(createHeadsStartValues(patternString
, invalidWildgetCharacter
));
137 * A Copy Constructor which creates a new {@link FileNameMatcher} with the
138 * same state and reset point like <code>other</code>.
141 * another {@link FileNameMatcher} instance.
143 public FileNameMatcher(FileNameMatcher other
) {
144 this(other
.headsStartValue
, other
.heads
);
147 private static List
<Head
> createHeadsStartValues(
148 final String patternString
, final Character invalidWildgetCharacter
)
149 throws InvalidPatternException
{
151 final List
<AbstractHead
> allHeads
= parseHeads(patternString
,
152 invalidWildgetCharacter
);
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
);
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.
164 nextHeadsSuggestion
.add(head
);
165 head
.setNewHeads(nextHeadsSuggestion
);
167 head
.setNewHeads(nextHeadsSuggestion
);
168 nextHeadsSuggestion
= new ArrayList
<Head
>(2);
169 nextHeadsSuggestion
.add(head
);
172 return nextHeadsSuggestion
;
175 private static int findGroupEnd(final int indexOfStartBracket
,
176 final String pattern
) throws InvalidPatternException
{
177 int firstValidCharClassIndex
= indexOfStartBracket
+ 1;
178 int firstValidEndBracketIndex
= indexOfStartBracket
+ 2;
180 if (indexOfStartBracket
+ 1 >= pattern
.length())
181 throw new NoClosingBracketException(indexOfStartBracket
, "[", "]",
184 if (pattern
.charAt(firstValidCharClassIndex
) == '!') {
185 firstValidCharClassIndex
++;
186 firstValidEndBracketIndex
++;
189 final Matcher charClassStartMatcher
= characterClassStartPattern
193 while (groupEnd
== -1) {
195 final int possibleGroupEnd
= pattern
.indexOf(']',
196 firstValidEndBracketIndex
);
197 if (possibleGroupEnd
== -1)
198 throw new NoClosingBracketException(indexOfStartBracket
, "[",
201 final boolean foundCharClass
= charClassStartMatcher
202 .find(firstValidCharClassIndex
);
205 && charClassStartMatcher
.start() < possibleGroupEnd
) {
207 final String classStart
= charClassStartMatcher
.group(0);
208 final String classEnd
= classStart
.charAt(1) + "]";
210 final int classStartIndex
= charClassStartMatcher
.start();
211 final int classEndIndex
= pattern
.indexOf(classEnd
,
212 classStartIndex
+ 2);
214 if (classEndIndex
== -1)
215 throw new NoClosingBracketException(classStartIndex
,
216 classStart
, classEnd
, pattern
);
218 firstValidCharClassIndex
= classEndIndex
+ 2;
219 firstValidEndBracketIndex
= firstValidCharClassIndex
;
221 groupEnd
= possibleGroupEnd
;
227 private static List
<AbstractHead
> parseHeads(final String pattern
,
228 final Character invalidWildgetCharacter
)
229 throws InvalidPatternException
{
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();
241 final String patternPart
= pattern
.substring(currentIndex
,
243 heads
.addAll(createSimpleHeads(patternPart
,
244 invalidWildgetCharacter
));
246 final int groupEnd
= findGroupEnd(groupStart
, pattern
);
247 final String groupPart
= pattern
.substring(groupStart
+ 1,
249 heads
.add(new GroupHead(groupPart
, pattern
));
250 currentIndex
= groupEnd
+ 1;
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
);
264 final AbstractHead head
= createWildCardHead(
265 invalidWildgetCharacter
, true);
270 final AbstractHead head
= createWildCardHead(
271 invalidWildgetCharacter
, false);
276 final CharacterHead head
= new CharacterHead(c
);
283 private static AbstractHead
createWildCardHead(
284 final Character invalidWildgetCharacter
, final boolean star
) {
285 if (invalidWildgetCharacter
!= null)
286 return new RestrictedWildCardHead(invalidWildgetCharacter
289 return new WildCardHead(star
);
292 private void extendStringToMatchByOneCharacter(final char c
) {
293 final List
<Head
> newHeads
= listForLocalUseage
;
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
;
309 listForLocalUseage
= heads
;
315 * @param stringToMatch
316 * extends the string which is matched against the patterns of
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
);
327 * Resets this matcher to it's state right after construction.
329 public void reset() {
331 heads
.addAll(headsStartValue
);
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.
340 public FileNameMatcher
createMatcherForSuffix() {
341 final List
<Head
> copyOfHeads
= new ArrayList
<Head
>(heads
.size());
342 copyOfHeads
.addAll(heads
);
343 return new FileNameMatcher(copyOfHeads
);
348 * @return true, if the string currently being matched does match.
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
) {
364 * @return false, if the string being matched will not match when the string
367 public boolean canAppendMatch() {
368 for (int i
= 0; i
< heads
.size(); i
++) {
369 if (heads
.get(i
) != LastHead
.INSTANCE
) {