FileNameMatcher.java
/*
* Copyright (C) 2008, Florian Köberle <florianskarten@web.de> and others
*
* This program and the accompanying materials are made available under the
* terms of the Eclipse Distribution License v. 1.0 which is available at
* https://www.eclipse.org/org/documents/edl-v10.php.
*
* SPDX-License-Identifier: BSD-3-Clause
*/
package org.eclipse.jgit.fnmatch;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.ListIterator;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import org.eclipse.jgit.errors.InvalidPatternException;
import org.eclipse.jgit.errors.NoClosingBracketException;
/**
* This class can be used to match filenames against fnmatch like patterns. It
* is not thread save.
* <p>
* Supported are the wildcard characters * and ? and groups with:
* <ul>
* <li>characters e.g. [abc]</li>
* <li>ranges e.g. [a-z]</li>
* <li>the following character classes
* <ul>
* <li>[:alnum:]</li>
* <li>[:alpha:]</li>
* <li>[:blank:]</li>
* <li>[:cntrl:]</li>
* <li>[:digit:]</li>
* <li>[:graph:]</li>
* <li>[:lower:]</li>
* <li>[:print:]</li>
* <li>[:punct:]</li>
* <li>[:space:]</li>
* <li>[:upper:]</li>
* <li>[:word:]</li>
* <li>[:xdigit:]</li>
* </ul>
* e. g. [[:xdigit:]]</li>
* </ul>
* Any character can be escaped by prepending it with a \
*/
public class FileNameMatcher {
static final List<Head> EMPTY_HEAD_LIST = Collections.emptyList();
private static final Pattern characterClassStartPattern = Pattern
.compile("\\[[.:=]"); //$NON-NLS-1$
private List<Head> headsStartValue;
private List<Head> heads;
/**
* {{@link #extendStringToMatchByOneCharacter(char)} needs a list for the
* new heads, allocating a new array would be bad for the performance, as
* the method gets called very often.
*
*/
private List<Head> listForLocalUseage;
/**
*
* @param headsStartValue
* must be a list which will never be modified.
*/
private FileNameMatcher(List<Head> headsStartValue) {
this(headsStartValue, headsStartValue);
}
/**
*
* @param headsStartValue
* must be a list which will never be modified.
* @param heads
* a list which will be cloned and then used as current head
* list.
*/
private FileNameMatcher(final List<Head> headsStartValue,
final List<Head> heads) {
this.headsStartValue = headsStartValue;
this.heads = new ArrayList<>(heads.size());
this.heads.addAll(heads);
this.listForLocalUseage = new ArrayList<>(heads.size());
}
/**
* Constructor for FileNameMatcher
*
* @param patternString
* must contain a pattern which fnmatch would accept.
* @param invalidWildgetCharacter
* if this parameter isn't null then this character will not
* match at wildcards(* and ? are wildcards).
* @throws org.eclipse.jgit.errors.InvalidPatternException
* if the patternString contains a invalid fnmatch pattern.
*/
public FileNameMatcher(final String patternString,
final Character invalidWildgetCharacter)
throws InvalidPatternException {
this(createHeadsStartValues(patternString, invalidWildgetCharacter));
}
/**
* A Copy Constructor which creates a new
* {@link org.eclipse.jgit.fnmatch.FileNameMatcher} with the same state and
* reset point like <code>other</code>.
*
* @param other
* another {@link org.eclipse.jgit.fnmatch.FileNameMatcher}
* instance.
*/
public FileNameMatcher(FileNameMatcher other) {
this(other.headsStartValue, other.heads);
}
private static List<Head> createHeadsStartValues(
final String patternString, final Character invalidWildgetCharacter)
throws InvalidPatternException {
final List<AbstractHead> allHeads = parseHeads(patternString,
invalidWildgetCharacter);
List<Head> nextHeadsSuggestion = new ArrayList<>(2);
nextHeadsSuggestion.add(LastHead.INSTANCE);
for (int i = allHeads.size() - 1; i >= 0; i--) {
final AbstractHead head = allHeads.get(i);
// explanation:
// a and * of the pattern "a*b"
// need *b as newHeads
// that's why * extends the list for it self and it's left neighbor.
if (head.isStar()) {
nextHeadsSuggestion.add(head);
head.setNewHeads(nextHeadsSuggestion);
} else {
head.setNewHeads(nextHeadsSuggestion);
nextHeadsSuggestion = new ArrayList<>(2);
nextHeadsSuggestion.add(head);
}
}
return nextHeadsSuggestion;
}
private static int findGroupEnd(final int indexOfStartBracket,
final String pattern) throws InvalidPatternException {
int firstValidCharClassIndex = indexOfStartBracket + 1;
int firstValidEndBracketIndex = indexOfStartBracket + 2;
if (indexOfStartBracket + 1 >= pattern.length())
throw new NoClosingBracketException(indexOfStartBracket, "[", "]", //$NON-NLS-1$ //$NON-NLS-2$
pattern);
if (pattern.charAt(firstValidCharClassIndex) == '!') {
firstValidCharClassIndex++;
firstValidEndBracketIndex++;
}
final Matcher charClassStartMatcher = characterClassStartPattern
.matcher(pattern);
int groupEnd = -1;
while (groupEnd == -1) {
final int possibleGroupEnd = indexOfUnescaped(pattern, ']',
firstValidEndBracketIndex);
if (possibleGroupEnd == -1)
throw new NoClosingBracketException(indexOfStartBracket, "[", //$NON-NLS-1$
"]", pattern); //$NON-NLS-1$
final boolean foundCharClass = charClassStartMatcher
.find(firstValidCharClassIndex);
if (foundCharClass
&& charClassStartMatcher.start() < possibleGroupEnd) {
final String classStart = charClassStartMatcher.group(0);
final String classEnd = classStart.charAt(1) + "]"; //$NON-NLS-1$
final int classStartIndex = charClassStartMatcher.start();
final int classEndIndex = pattern.indexOf(classEnd,
classStartIndex + 2);
if (classEndIndex == -1)
throw new NoClosingBracketException(classStartIndex,
classStart, classEnd, pattern);
firstValidCharClassIndex = classEndIndex + 2;
firstValidEndBracketIndex = firstValidCharClassIndex;
} else {
groupEnd = possibleGroupEnd;
}
}
return groupEnd;
}
private static List<AbstractHead> parseHeads(final String pattern,
final Character invalidWildgetCharacter)
throws InvalidPatternException {
int currentIndex = 0;
List<AbstractHead> heads = new ArrayList<>();
while (currentIndex < pattern.length()) {
final int groupStart = indexOfUnescaped(pattern, '[', currentIndex);
if (groupStart == -1) {
final String patternPart = pattern.substring(currentIndex);
heads.addAll(createSimpleHeads(patternPart,
invalidWildgetCharacter));
currentIndex = pattern.length();
} else {
final String patternPart = pattern.substring(currentIndex,
groupStart);
heads.addAll(createSimpleHeads(patternPart,
invalidWildgetCharacter));
final int groupEnd = findGroupEnd(groupStart, pattern);
final String groupPart = pattern.substring(groupStart + 1,
groupEnd);
heads.add(new GroupHead(groupPart, pattern));
currentIndex = groupEnd + 1;
}
}
return heads;
}
private static List<AbstractHead> createSimpleHeads(
final String patternPart, final Character invalidWildgetCharacter) {
final List<AbstractHead> heads = new ArrayList<>(
patternPart.length());
boolean escaped = false;
for (int i = 0; i < patternPart.length(); i++) {
final char c = patternPart.charAt(i);
if (escaped) {
final CharacterHead head = new CharacterHead(c);
heads.add(head);
escaped = false;
} else {
switch (c) {
case '*': {
final AbstractHead head = createWildCardHead(
invalidWildgetCharacter, true);
heads.add(head);
break;
}
case '?': {
final AbstractHead head = createWildCardHead(
invalidWildgetCharacter, false);
heads.add(head);
break;
}
case '\\':
escaped = true;
break;
default:
final CharacterHead head = new CharacterHead(c);
heads.add(head);
}
}
}
return heads;
}
private static AbstractHead createWildCardHead(
final Character invalidWildgetCharacter, final boolean star) {
if (invalidWildgetCharacter != null) {
return new RestrictedWildCardHead(invalidWildgetCharacter
.charValue(), star);
}
return new WildCardHead(star);
}
/**
* @param c new character to append
* @return true to continue, false if the matcher can stop appending
*/
private boolean extendStringToMatchByOneCharacter(char c) {
final List<Head> newHeads = listForLocalUseage;
newHeads.clear();
List<Head> lastAddedHeads = null;
for (int i = 0; i < heads.size(); i++) {
final Head head = heads.get(i);
final List<Head> headsToAdd = head.getNextHeads(c);
// Why the next performance optimization isn't wrong:
// Some times two heads return the very same list.
// We save future effort if we don't add these heads again.
// This is the case with the heads "a" and "*" of "a*b" which
// both can return the list ["*","b"]
if (headsToAdd != lastAddedHeads) {
if (!headsToAdd.isEmpty())
newHeads.addAll(headsToAdd);
lastAddedHeads = headsToAdd;
}
}
listForLocalUseage = heads;
heads = newHeads;
return !newHeads.isEmpty();
}
private static int indexOfUnescaped(final String searchString,
final char ch, final int fromIndex) {
for (int i = fromIndex; i < searchString.length(); i++) {
char current = searchString.charAt(i);
if (current == ch)
return i;
if (current == '\\')
i++; // Skip the next char as it is escaped }
}
return -1;
}
/**
* Append to the string which is matched against the patterns of this class
*
* @param stringToMatch
* extends the string which is matched against the patterns of
* this class.
*/
public void append(String stringToMatch) {
for (int i = 0; i < stringToMatch.length(); i++) {
final char c = stringToMatch.charAt(i);
if (!extendStringToMatchByOneCharacter(c))
break;
}
}
/**
* Resets this matcher to it's state right after construction.
*/
public void reset() {
heads.clear();
heads.addAll(headsStartValue);
}
/**
* Create a {@link org.eclipse.jgit.fnmatch.FileNameMatcher} instance which
* uses the same pattern like this matcher, but has the current state of
* this matcher as reset and start point
*
* @return a {@link org.eclipse.jgit.fnmatch.FileNameMatcher} instance which
* uses the same pattern like this matcher, but has the current
* state of this matcher as reset and start point.
*/
public FileNameMatcher createMatcherForSuffix() {
final List<Head> copyOfHeads = new ArrayList<>(heads.size());
copyOfHeads.addAll(heads);
return new FileNameMatcher(copyOfHeads);
}
/**
* Whether the matcher matches
*
* @return whether the matcher matches
*/
public boolean isMatch() {
if (heads.isEmpty())
return false;
final ListIterator<Head> headIterator = heads
.listIterator(heads.size());
while (headIterator.hasPrevious()) {
final Head head = headIterator.previous();
if (head == LastHead.INSTANCE) {
return true;
}
}
return false;
}
/**
* Whether a match can be appended
*
* @return a boolean.
*/
public boolean canAppendMatch() {
for (Head head : heads) {
if (head != LastHead.INSTANCE) {
return true;
}
}
return false;
}
}