[JGIT PATCH v3 02/23] Added the class FileNameMatcher and a test class for it.
Signed-off-by: Florian Koeberle <florianskarten@web.de>
---
.../org/spearce/jgit/lib/FileNameMatcherTest.java | 311 ++++++++++++++++
.../src/org/spearce/jgit/lib/FileNameMatcher.java | 376 ++++++++++++++++++++
2 files changed, 687 insertions(+), 0 deletions(-)
create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/lib/FileNameMatcherTest.java
create mode 100644 org.spearce.jgit/src/org/spearce/jgit/lib/FileNameMatcher.java
diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/FileNameMatcherTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/FileNameMatcherTest.java
new file mode 100644
index 0000000..fb0d8b2
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/FileNameMatcherTest.java
@@ -0,0 +1,311 @@
+package org.spearce.jgit.lib;
+
+import org.spearce.jgit.errors.InvalidPatternException;
+
+import junit.framework.TestCase;
+
+public class FileNameMatcherTest extends TestCase {
+
+ private void assertMatch(final String pattern, final String input,
+ final boolean matchExpected,
+ final boolean extendResultInNoMatchExpected)
+ throws InvalidPatternException {
+ final FileNameMatcher matcher = new FileNameMatcher(pattern, null);
+ matcher.extendStringToMatch(input);
+ assertEquals(matchExpected, matcher.isMatch());
+ assertEquals(extendResultInNoMatchExpected, matcher
+ .willExtendResultInNoMatch());
+ }
+
+ private void assertFileNameMatch(final String pattern, final String input,
+ final char excludedCharacter, final boolean matchExpected,
+ final boolean extendResultInNoMatchExpected)
+ throws InvalidPatternException {
+ final FileNameMatcher matcher = new FileNameMatcher(pattern,
+ new Character(excludedCharacter));
+ matcher.extendStringToMatch(input);
+ assertEquals(matchExpected, matcher.isMatch());
+ assertEquals(extendResultInNoMatchExpected, matcher
+ .willExtendResultInNoMatch());
+ }
+
+ public void testVerySimplePatternCase0() throws Exception {
+ assertMatch("", "", true, true);
+ }
+
+ public void testVerySimplePatternCase1() throws Exception {
+ assertMatch("ab", "a", false, false);
+ }
+
+ public void testVerySimplePatternCase2() throws Exception {
+ assertMatch("ab", "ab", true, true);
+ }
+
+ public void testVerySimplePatternCase3() throws Exception {
+ assertMatch("ab", "ac", false, true);
+ }
+
+ public void testVerySimplePatternCase4() throws Exception {
+ assertMatch("ab", "abc", false, true);
+ }
+
+ public void testVerySimpleWirdcardCase0() throws Exception {
+ assertMatch("?", "a", true, true);
+ }
+
+ public void testVerySimpleWildCardCase1() throws Exception {
+ assertMatch("??", "a", false, false);
+ }
+
+ public void testVerySimpleWildCardCase2() throws Exception {
+ assertMatch("??", "ab", true, true);
+ }
+
+ public void testVerySimpleWildCardCase3() throws Exception {
+ assertMatch("??", "abc", false, true);
+ }
+
+ public void testVerySimpleStarCase0() throws Exception {
+ assertMatch("*", "", true, false);
+ }
+
+ public void testVerySimpleStarCase1() throws Exception {
+ assertMatch("*", "a", true, false);
+ }
+
+ public void testVerySimpleStarCase2() throws Exception {
+ assertMatch("*", "ab", true, false);
+ }
+
+ public void testSimpleStarCase0() throws Exception {
+ assertMatch("a*b", "a", false, false);
+ }
+
+ public void testSimpleStarCase1() throws Exception {
+ assertMatch("a*c", "ac", true, false);
+ }
+
+ public void testSimpleStarCase2() throws Exception {
+ assertMatch("a*c", "ab", false, false);
+ }
+
+ public void testSimpleStarCase3() throws Exception {
+ assertMatch("a*c", "abc", true, false);
+ }
+
+ public void testManySolutionsCase0() throws Exception {
+ assertMatch("a*a*a", "aaa", true, false);
+ }
+
+ public void testManySolutionsCase1() throws Exception {
+ assertMatch("a*a*a", "aaaa", true, false);
+ }
+
+ public void testManySolutionsCase2() throws Exception {
+ assertMatch("a*a*a", "ababa", true, false);
+ }
+
+ public void testManySolutionsCase3() throws Exception {
+ assertMatch("a*a*a", "aaaaaaaa", true, false);
+ }
+
+ public void testManySolutionsCase4() throws Exception {
+ assertMatch("a*a*a", "aaaaaaab", false, false);
+ }
+
+ public void testVerySimpleGroupCase0() throws Exception {
+ assertMatch("[ab]", "a", true, true);
+ }
+
+ public void testVerySimpleGroupCase1() throws Exception {
+ assertMatch("[ab]", "b", true, true);
+ }
+
+ public void testVerySimpleGroupCase2() throws Exception {
+ assertMatch("[ab]", "ab", false, true);
+ }
+
+ public void testVerySimpleGroupRangeCase0() throws Exception {
+ assertMatch("[b-d]", "a", false, true);
+ }
+
+ public void testVerySimpleGroupRangeCase1() throws Exception {
+ assertMatch("[b-d]", "b", true, true);
+ }
+
+ public void testVerySimpleGroupRangeCase2() throws Exception {
+ assertMatch("[b-d]", "c", true, true);
+ }
+
+ public void testVerySimpleGroupRangeCase3() throws Exception {
+ assertMatch("[b-d]", "d", true, true);
+ }
+
+ public void testVerySimpleGroupRangeCase4() throws Exception {
+ assertMatch("[b-d]", "e", false, true);
+ }
+
+ public void testVerySimpleGroupRangeCase5() throws Exception {
+ assertMatch("[b-d]", "-", false, true);
+ }
+
+ public void testTwoGroupsCase0() throws Exception {
+ assertMatch("[b-d][ab]", "bb", true, true);
+ }
+
+ public void testTwoGroupsCase1() throws Exception {
+ assertMatch("[b-d][ab]", "ca", true, true);
+ }
+
+ public void testTwoGroupsCase2() throws Exception {
+ assertMatch("[b-d][ab]", "fa", false, true);
+ }
+
+ public void testTwoGroupsCase3() throws Exception {
+ assertMatch("[b-d][ab]", "bc", false, true);
+ }
+
+ public void testTwoRangesInOneGroupCase0() throws Exception {
+ assertMatch("[b-ce-e]", "a", false, true);
+ }
+
+ public void testTwoRangesInOneGroupCase1() throws Exception {
+ assertMatch("[b-ce-e]", "b", true, true);
+ }
+
+ public void testTwoRangesInOneGroupCase2() throws Exception {
+ assertMatch("[b-ce-e]", "c", true, true);
+ }
+
+ public void testTwoRangesInOneGroupCase3() throws Exception {
+ assertMatch("[b-ce-e]", "d", false, true);
+ }
+
+ public void testTwoRangesInOneGroupCase4() throws Exception {
+ assertMatch("[b-ce-e]", "e", true, true);
+ }
+
+ public void testTwoRangesInOneGroupCase5() throws Exception {
+ assertMatch("[b-ce-e]", "f", false, true);
+ }
+
+ public void testIncompleteRangesInOneGroupCase0() throws Exception {
+ assertMatch("a[b-]", "ab", true, true);
+ }
+
+ public void testIncompleteRangesInOneGroupCase1() throws Exception {
+ assertMatch("a[b-]", "ac", false, true);
+ }
+
+ public void testIncompleteRangesInOneGroupCase2() throws Exception {
+ assertMatch("a[b-]", "a-", true, true);
+ }
+
+ public void testCombinedRangesInOneGroupCase0() throws Exception {
+ assertMatch("[a-c-e]", "b", true, true);
+ }
+
+ /**
+ * The c belongs to the range a-c. "-e" is no valid range so d should not
+ * match.
+ *
+ * @throws Exception
+ * for some reasons
+ */
+ public void testCombinedRangesInOneGroupCase1() throws Exception {
+ assertMatch("[a-c-e]", "d", false, true);
+ }
+
+ public void testCombinedRangesInOneGroupCase2() throws Exception {
+ assertMatch("[a-c-e]", "e", true, true);
+ }
+
+ public void testInversedGroupCase0() throws Exception {
+ assertMatch("[!b-c]", "a", true, true);
+ }
+
+ public void testInversedGroupCase1() throws Exception {
+ assertMatch("[!b-c]", "b", false, true);
+ }
+
+ public void testInversedGroupCase2() throws Exception {
+ assertMatch("[!b-c]", "c", false, true);
+ }
+
+ public void testInversedGroupCase3() throws Exception {
+ assertMatch("[!b-c]", "d", true, true);
+ }
+
+ public void testFilePathSimpleCase() throws Exception {
+ assertFileNameMatch("a/b", "a/b", '/', true, true);
+ }
+
+ public void testFilePathCase0() throws Exception {
+ assertFileNameMatch("a*b", "a/b", '/', false, true);
+ }
+
+ public void testFilePathCase1() throws Exception {
+ assertFileNameMatch("a?b", "a/b", '/', false, true);
+ }
+
+ public void testFilePathCase2() throws Exception {
+ assertFileNameMatch("a*b", "a\\b", '\\', false, true);
+ }
+
+ public void testFilePathCase3() throws Exception {
+ assertFileNameMatch("a?b", "a\\b", '\\', false, true);
+ }
+
+ public void testReset() throws Exception {
+ final String pattern = "helloworld";
+ final FileNameMatcher matcher = new FileNameMatcher(pattern, null);
+ matcher.extendStringToMatch("helloworld");
+ assertEquals(true, matcher.isMatch());
+ assertEquals(true, matcher.willExtendResultInNoMatch());
+ matcher.resetStringToMatch();
+ matcher.extendStringToMatch("hello");
+ assertEquals(false, matcher.isMatch());
+ assertEquals(false, matcher.willExtendResultInNoMatch());
+ matcher.extendStringToMatch("world");
+ assertEquals(true, matcher.isMatch());
+ assertEquals(true, matcher.willExtendResultInNoMatch());
+ matcher.extendStringToMatch("to much");
+ assertEquals(false, matcher.isMatch());
+ assertEquals(true, matcher.willExtendResultInNoMatch());
+ matcher.resetStringToMatch();
+ matcher.extendStringToMatch("helloworld");
+ assertEquals(true, matcher.isMatch());
+ assertEquals(true, matcher.willExtendResultInNoMatch());
+ }
+
+ public void testCreateMatcherForSuffix() throws Exception {
+ final String pattern = "helloworld";
+ final FileNameMatcher matcher = new FileNameMatcher(pattern, null);
+ matcher.extendStringToMatch("hello");
+ final FileNameMatcher childMatcher = matcher.createMatcherForSuffix();
+ assertEquals(false, matcher.isMatch());
+ assertEquals(false, matcher.willExtendResultInNoMatch());
+ assertEquals(false, childMatcher.isMatch());
+ assertEquals(false, childMatcher.willExtendResultInNoMatch());
+ matcher.extendStringToMatch("world");
+ assertEquals(true, matcher.isMatch());
+ assertEquals(true, matcher.willExtendResultInNoMatch());
+ assertEquals(false, childMatcher.isMatch());
+ assertEquals(false, childMatcher.willExtendResultInNoMatch());
+ childMatcher.extendStringToMatch("world");
+ assertEquals(true, matcher.isMatch());
+ assertEquals(true, matcher.willExtendResultInNoMatch());
+ assertEquals(true, childMatcher.isMatch());
+ assertEquals(true, childMatcher.willExtendResultInNoMatch());
+ childMatcher.resetStringToMatch();
+ assertEquals(true, matcher.isMatch());
+ assertEquals(true, matcher.willExtendResultInNoMatch());
+ assertEquals(false, childMatcher.isMatch());
+ assertEquals(false, childMatcher.willExtendResultInNoMatch());
+ childMatcher.extendStringToMatch("world");
+ assertEquals(true, matcher.isMatch());
+ assertEquals(true, matcher.willExtendResultInNoMatch());
+ assertEquals(true, childMatcher.isMatch());
+ assertEquals(true, childMatcher.willExtendResultInNoMatch());
+ }
+}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/FileNameMatcher.java b/org.spearce.jgit/src/org/spearce/jgit/lib/FileNameMatcher.java
new file mode 100644
index 0000000..4177e27
--- /dev/null
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/FileNameMatcher.java
@@ -0,0 +1,376 @@
+package org.spearce.jgit.lib;
+
+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.spearce.jgit.errors.InvalidPatternException;
+
+/**
+ * This class can be used to match filenames against fnmatch like patterns. It
+ * is not thread save.
+ */
+public class FileNameMatcher {
+ private static final List<Head> EMPTY_HEAD_LIST = Collections.emptyList();
+
+ 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(final List<Head> headsStartValue) {
+ this.headsStartValue = headsStartValue;
+ this.heads = new ArrayList<Head>(headsStartValue.size());
+ this.heads.addAll(this.headsStartValue);
+ this.listForLocalUseage = new ArrayList<Head>(headsStartValue.size());
+ }
+
+ /**
+ * @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 InvalidPatternException
+ * if the patternString contains a invalid fnmatch pattern.
+ */
+ public FileNameMatcher(final String patternString,
+ final Character invalidWildgetCharacter)
+ throws InvalidPatternException {
+ this(createHeadsStartValues(patternString, invalidWildgetCharacter));
+ }
+
+ private static List<Head> createHeadsStartValues(
+ final String patternString, final Character invalidWildgetCharacter)
+ throws InvalidPatternException {
+ List<Head> nextHeadsSuggestion = new ArrayList<Head>(2);
+ nextHeadsSuggestion.add(LastHead.INSTANCE);
+
+ final char previosChracter = '\n';
+ int i = patternString.length() - 1;
+ while (i >= 0) {
+ final char c = patternString.charAt(i);
+
+ switch (c) {
+ case '*': {
+ if (previosChracter != '*') {
+ final AbstractHead head = createWildCardHead(invalidWildgetCharacter);
+ nextHeadsSuggestion.add(head);
+ head.setNewHeads(nextHeadsSuggestion);
+ }
+ break;
+ }
+ case '?': {
+ final AbstractHead head = createWildCardHead(invalidWildgetCharacter);
+ head.setNewHeads(nextHeadsSuggestion);
+ nextHeadsSuggestion = new ArrayList<Head>(2);
+ nextHeadsSuggestion.add(head);
+ break;
+ }
+ case ']': {
+ final String groupPattern = extractGroupPatternWithoutBrackets(
+ patternString, i);
+ i -= groupPattern.length() + 1;
+ final AbstractHead head = new GroupHead(groupPattern);
+ head.setNewHeads(nextHeadsSuggestion);
+ nextHeadsSuggestion = new ArrayList<Head>(2);
+ nextHeadsSuggestion.add(head);
+ break;
+ }
+ case '[': {
+ final String message = String
+ .format("There is no closing ] for the character [ at "
+ + i);
+ throw new InvalidPatternException(message, patternString);
+ }
+ default: {
+ final CharacterHead head = new CharacterHead(c);
+ head.setNewHeads(nextHeadsSuggestion);
+ nextHeadsSuggestion = new ArrayList<Head>(2);
+ nextHeadsSuggestion.add(head);
+ }
+ }
+ i--;
+
+ }
+ return nextHeadsSuggestion;
+ }
+
+ private static String extractGroupPatternWithoutBrackets(
+ final String patternString, int closingBracketIndex)
+ throws InvalidPatternException {
+ int start = closingBracketIndex - 1;
+ while (start >= 0) {
+ final char possibleStartCharacter = patternString.charAt(start);
+ if (possibleStartCharacter == '[') {
+ break;
+ }
+ if (possibleStartCharacter == ']') {
+ final String message = String
+ .format(
+ "Found two ] characters at %s and %s without a [ character between.",
+ String.valueOf(start), String
+ .valueOf(closingBracketIndex));
+ throw new InvalidPatternException(message, patternString);
+ }
+ start--;
+ }
+ if (start < 0) {
+ final String message = String
+ .format(
+ "Found a ] character at %s but no [ character infront of it.",
+ String.valueOf(closingBracketIndex));
+ throw new InvalidPatternException(message, patternString);
+ }
+ final String groupPatternWithOutBrackets = patternString.substring(
+ start + 1, closingBracketIndex);
+ return groupPatternWithOutBrackets;
+ }
+
+ private static AbstractHead createWildCardHead(
+ final Character invalidWildgetCharacter) {
+ if (invalidWildgetCharacter != null)
+ return new RestrictedWildCardHead(invalidWildgetCharacter
+ .charValue());
+ else
+ return new WildCardHead();
+ }
+
+ private void extendStringToMatchByOneCharacter(final 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) {
+ newHeads.addAll(headsToAdd);
+ lastAddedHeads = headsToAdd;
+ }
+ }
+ listForLocalUseage = heads;
+ heads = newHeads;
+ }
+
+ /**
+ *
+ * @param stringToMatch
+ * extends the string which is matched against the patterns of
+ * this class.
+ */
+ public void extendStringToMatch(final String stringToMatch) {
+ for (int i = 0; i < stringToMatch.length(); i++) {
+ final char c = stringToMatch.charAt(i);
+ extendStringToMatchByOneCharacter(c);
+ }
+ }
+
+ /**
+ * Resets this matcher to it's state right after construction.
+ */
+ public void resetStringToMatch() {
+ heads.clear();
+ heads.addAll(headsStartValue);
+ }
+
+ /**
+ *
+ * @return a {@link 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<Head>(heads.size());
+ copyOfHeads.addAll(heads);
+ return new FileNameMatcher(copyOfHeads);
+ }
+
+ private interface Head {
+ /**
+ *
+ * @param c
+ * the character which decides which heads are returned.
+ * @return a list of heads based on the input.
+ */
+ public abstract List<Head> getNextHeads(char c);
+ }
+
+ private static abstract class AbstractHead implements Head {
+ private List<Head> newHeads = null;
+
+ protected abstract boolean matches(char c);
+
+ /**
+ *
+ * @param newHeads
+ * a list of {@link Head}s which will not be modified.
+ */
+ public final void setNewHeads(List<Head> newHeads) {
+ if (this.newHeads != null)
+ throw new IllegalStateException("Property is already non null");
+ this.newHeads = newHeads;
+ }
+
+ public List<Head> getNextHeads(char c) {
+ if (matches(c))
+ return newHeads;
+ else
+ return EMPTY_HEAD_LIST;
+ }
+ }
+
+ private static final class LastHead implements Head {
+ static final Head INSTANCE = new LastHead();
+
+ /**
+ * Don't call this constructor, use {@link #INSTANCE}
+ */
+ private LastHead() {
+ // defined because of javadoc and visibility modifier.
+ }
+
+ public List<Head> getNextHeads(char c) {
+ return EMPTY_HEAD_LIST;
+ }
+
+ }
+
+ private static final class CharacterHead extends AbstractHead {
+ private final char expectedCharacter;
+
+ protected CharacterHead(final char expectedCharacter) {
+ this.expectedCharacter = expectedCharacter;
+ }
+
+ @Override
+ protected final boolean matches(final char c) {
+ return c == expectedCharacter;
+ }
+
+ }
+
+ private static final class WildCardHead extends AbstractHead {
+ @Override
+ protected final boolean matches(final char c) {
+ return true;
+ }
+ }
+
+ private static final class RestrictedWildCardHead extends AbstractHead {
+ private final char excludedCharacter;
+
+ RestrictedWildCardHead(final char excludedCharacter) {
+ this.excludedCharacter = excludedCharacter;
+ }
+
+ @Override
+ protected final boolean matches(final char c) {
+ return c != excludedCharacter;
+ }
+ }
+
+ private static final class GroupHead extends AbstractHead {
+ private final List<CharacterRange> ranges;
+
+ private final boolean inverse;
+
+ GroupHead(String pattern) {
+ this.ranges = new ArrayList<CharacterRange>();
+ this.inverse = pattern.startsWith("!");
+ if (inverse) {
+ pattern = pattern.substring(1);
+ }
+ final Pattern regexPattern = Pattern.compile("[^-][-][^-]");
+ final Matcher matcher = regexPattern.matcher(pattern);
+ while (matcher.find()) {
+ final String rangeString = matcher.group(0);
+ final char start = rangeString.charAt(0);
+ final char end = rangeString.charAt(2);
+ ranges.add(new CharacterRange(start, end));
+ pattern = matcher.replaceFirst("");
+ matcher.reset(pattern);
+ }
+ // pattern contains now no ranges
+ for (int i = 0; i < pattern.length(); i++) {
+ final char c = pattern.charAt(i);
+ ranges.add(new CharacterRange(c, c));
+ }
+ }
+
+ @Override
+ protected final boolean matches(final char c) {
+ for (CharacterRange range : ranges) {
+ if (range.inRange(c)) {
+ return !inverse;
+ }
+ }
+ return inverse;
+ }
+
+ private static final class CharacterRange {
+ private final char start;
+
+ private final char end;
+
+ CharacterRange(char start, char end) {
+ this.start = start;
+ this.end = end;
+ }
+
+ boolean inRange(char c) {
+ return start <= c && c <= end;
+ }
+
+ }
+ }
+
+ /**
+ *
+ * @return true, if the string currently beeing matched does match.
+ */
+ public boolean isMatch() {
+ final ListIterator<Head> headIterator = heads
+ .listIterator(heads.size());
+ while (headIterator.hasPrevious()) {
+ final Head head = headIterator.previous();
+ if (head == LastHead.INSTANCE) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /**
+ *
+ * @return true, if the string beeing matched will not match when the string
+ * gets extended.
+ */
+ public boolean willExtendResultInNoMatch() {
+ for (int i = 0; i < heads.size(); i++) {
+ if (heads.get(i) != LastHead.INSTANCE) {
+ return false;
+ }
+ }
+ return true;
+ }
+}
--
1.5.4.3