Reimplementation of ignore rule parser

The current IgnoreRule/FileNameMatcher implementation scales not well
with huge repositories - it is both slow and memory expensive while
parsing glob expressions (bug 440732). Addtitionally, the "double star"
pattern (/**/) is not understood by the old parser (bug 416348).

The proposed implementation is a complete clean room rewrite of the
gitignore parser, aiming to add missing double star pattern support and
improve the performance and memory consumption.

The glob expressions from .gitignore rules are converted to Java regular
expressions (java.util.regex.Pattern). java.util.regex.Pattern code can
evaluate expression from gitignore rules considerable faster (and with
less memory consumption) as the old FileNameMatcher implementation.

CQ: 8828
Bug: 416348
Bug: 440732
Change-Id: Ibefb930381f2f16eddb9947e592752f8ae2b76e1
Signed-off-by: Andrey Loskutov <loskutov@gmx.de>
Signed-off-by: Matthias Sohn <matthias.sohn@sap.com>

12 files changed, 1287 insertions, 11 deletions

diff --git a/org.eclipse.jgit/META-INF/MANIFEST.MF b/org.eclipse.jgit/META-INF/MANIFEST.MF
index 9cbb9955f2..80399f6008 100644
--- a/org.eclipse.jgit/META-INF/MANIFEST.MF
+++ b/org.eclipse.jgit/META-INF/MANIFEST.MF
@@ -50,6 +50,7 @@ Export-Package: org.eclipse.jgit.api;version="3.6.0";
    org.eclipse.jgit.lib",
  org.eclipse.jgit.gitrepo.internal;version="3.6.0";x-internal:=true,
  org.eclipse.jgit.ignore;version="3.6.0",
+ org.eclipse.jgit.ignore.internal;version="3.6.0";x-friends:="org.eclipse.jgit.test",
  org.eclipse.jgit.internal;version="3.6.0";x-friends:="org.eclipse.jgit.test,org.eclipse.jgit.http.test",
  org.eclipse.jgit.internal.storage.dfs;version="3.6.0";x-friends:="org.eclipse.jgit.test",
  org.eclipse.jgit.internal.storage.file;version="3.6.0";
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/ignore/FastIgnoreRule.java b/org.eclipse.jgit/src/org/eclipse/jgit/ignore/FastIgnoreRule.java
new file mode 100644
index 0000000000..02863bd16a
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/ignore/FastIgnoreRule.java
@@ -0,0 +1,229 @@
+/*
+ * Copyright (C) 2014, Andrey Loskutov <loskutov@gmx.de>
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+package org.eclipse.jgit.ignore;
+
+import static org.eclipse.jgit.ignore.internal.Strings.stripTrailing;
+
+import org.eclipse.jgit.errors.InvalidPatternException;
+import org.eclipse.jgit.ignore.internal.IMatcher;
+import org.eclipse.jgit.ignore.internal.PathMatcher;
+
+/**
+ * "Fast" (compared with IgnoreRule) git ignore rule implementation supporting
+ * also double star <code>**<code> pattern.
+ * <p>
+ * This class is immutable and thread safe.
+ *
+ * @since 3.6
+ */
+public class FastIgnoreRule {
+
+	/**
+	 * Character used as default path separator for ignore entries
+	 */
+	public static final char PATH_SEPARATOR = '/';
+
+	private static final NoResultMatcher NO_MATCH = new NoResultMatcher();
+
+	private final IMatcher matcher;
+
+	private final boolean inverse;
+
+	private final boolean dirOnly;
+
+	/**
+	 *
+	 * @param pattern
+	 *            ignore pattern as described in <a href=
+	 *            "https://www.kernel.org/pub/software/scm/git/docs/gitignore.html"
+	 *            >git manual</a>. If pattern is invalid or is not a pattern
+	 *            (comment), this rule doesn't match anything.
+	 */
+	public FastIgnoreRule(String pattern) {
+		if (pattern == null)
+			throw new IllegalArgumentException("Pattern must not be null!"); //$NON-NLS-1$
+		if (pattern.length() == 0) {
+			dirOnly = false;
+			inverse = false;
+			this.matcher = NO_MATCH;
+			return;
+		}
+		inverse = pattern.charAt(0) == '!';
+		if (inverse) {
+			pattern = pattern.substring(1);
+			if (pattern.length() == 0) {
+				dirOnly = false;
+				this.matcher = NO_MATCH;
+				return;
+			}
+		}
+		if (pattern.charAt(0) == '#') {
+			this.matcher = NO_MATCH;
+			dirOnly = false;
+		} else {
+			dirOnly = pattern.charAt(pattern.length() - 1) == PATH_SEPARATOR;
+			if (dirOnly) {
+				pattern = stripTrailing(pattern, PATH_SEPARATOR);
+				if (pattern.length() == 0) {
+					this.matcher = NO_MATCH;
+					return;
+				}
+			}
+			IMatcher m;
+			try {
+				m = PathMatcher.createPathMatcher(pattern,
+						Character.valueOf(PATH_SEPARATOR), dirOnly);
+			} catch (InvalidPatternException e) {
+				m = NO_MATCH;
+			}
+			this.matcher = m;
+		}
+	}
+
+	/**
+	 * Returns true if a match was made. <br>
+	 * This function does NOT return the actual ignore status of the target!
+	 * Please consult {@link #getResult()} for the negation status. The actual
+	 * ignore status may be true or false depending on whether this rule is an
+	 * ignore rule or a negation rule.
+	 *
+	 * @param path
+	 *            Name pattern of the file, relative to the base directory of
+	 *            this rule
+	 * @param directory
+	 *            Whether the target file is a directory or not
+	 * @return True if a match was made. This does not necessarily mean that the
+	 *         target is ignored. Call {@link #getResult() getResult()} for the
+	 *         result.
+	 */
+	public boolean isMatch(String path, boolean directory) {
+		if (path == null)
+			return false;
+		if (path.length() == 0)
+			return false;
+		boolean match = matcher.matches(path, directory);
+		return match;
+	}
+
+	/**
+	 * @return True if the pattern is just a file name and not a path
+	 */
+	public boolean getNameOnly() {
+		return !(matcher instanceof PathMatcher);
+	}
+
+	/**
+	 *
+	 * @return True if the pattern should match directories only
+	 */
+	public boolean dirOnly() {
+		return dirOnly;
+	}
+
+	/**
+	 * Indicates whether the rule is non-negation or negation.
+	 *
+	 * @return True if the pattern had a "!" in front of it
+	 */
+	public boolean getNegation() {
+		return inverse;
+	}
+
+	/**
+	 * Indicates whether the rule is non-negation or negation.
+	 *
+	 * @return True if the target is to be ignored, false otherwise.
+	 */
+	public boolean getResult() {
+		return !inverse;
+	}
+
+	@Override
+	public String toString() {
+		StringBuilder sb = new StringBuilder();
+		if (inverse)
+			sb.append('!');
+		sb.append(matcher);
+		if (dirOnly)
+			sb.append(PATH_SEPARATOR);
+		return sb.toString();
+
+	}
+
+	@Override
+	public int hashCode() {
+		final int prime = 31;
+		int result = 1;
+		result = prime * result + (inverse ? 1231 : 1237);
+		result = prime * result + (dirOnly ? 1231 : 1237);
+		result = prime * result + ((matcher == null) ? 0 : matcher.hashCode());
+		return result;
+	}
+
+	@Override
+	public boolean equals(Object obj) {
+		if (this == obj)
+			return true;
+		if (!(obj instanceof FastIgnoreRule))
+			return false;
+
+		FastIgnoreRule other = (FastIgnoreRule) obj;
+		if (inverse != other.inverse)
+			return false;
+		if (dirOnly != other.dirOnly)
+			return false;
+		return matcher.equals(other.matcher);
+	}
+
+	static final class NoResultMatcher implements IMatcher {
+
+		public boolean matches(String path, boolean assumeDirectory) {
+			return false;
+		}
+
+		public boolean matches(String segment, int startIncl, int endExcl,
+				boolean assumeDirectory) {
+			return false;
+		}
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/ignore/IgnoreNode.java b/org.eclipse.jgit/src/org/eclipse/jgit/ignore/IgnoreNode.java
index 2cddddbe11..ff74f7cabf 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/ignore/IgnoreNode.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/ignore/IgnoreNode.java
@@ -71,11 +71,11 @@ public class IgnoreNode {
 	}
 
 	/** The rules that have been parsed into this node. */
-	private final List<IgnoreRule> rules;
+	private final List<FastIgnoreRule> rules;
 
 	/** Create an empty ignore node with no rules. */
 	public IgnoreNode() {
-		rules = new ArrayList<IgnoreRule>();
+		rules = new ArrayList<FastIgnoreRule>();
 	}
 
 	/**
@@ -84,7 +84,7 @@ public class IgnoreNode {
 	 * @param rules
 	 *            list of rules.
 	 **/
-	public IgnoreNode(List<IgnoreRule> rules) {
+	public IgnoreNode(List<FastIgnoreRule> rules) {
 		this.rules = rules;
 	}
 
@@ -103,7 +103,7 @@ public class IgnoreNode {
 		while ((txt = br.readLine()) != null) {
 			txt = txt.trim();
 			if (txt.length() > 0 && !txt.startsWith("#") && !txt.equals("/")) //$NON-NLS-1$ //$NON-NLS-2$
-				rules.add(new IgnoreRule(txt));
+				rules.add(new FastIgnoreRule(txt));
 		}
 	}
 
@@ -112,7 +112,7 @@ public class IgnoreNode {
 	}
 
 	/** @return list of all ignore rules held by this node. */
-	public List<IgnoreRule> getRules() {
+	public List<FastIgnoreRule> getRules() {
 		return Collections.unmodifiableList(rules);
 	}
 
@@ -133,7 +133,7 @@ public class IgnoreNode {
 
 		// Parse rules in the reverse order that they were read
 		for (int i = rules.size() - 1; i > -1; i--) {
-			IgnoreRule rule = rules.get(i);
+			FastIgnoreRule rule = rules.get(i);
 			if (rule.isMatch(entryPath, isDirectory)) {
 				if (rule.getResult())
 					return MatchResult.IGNORED;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/ignore/IgnoreRule.java b/org.eclipse.jgit/src/org/eclipse/jgit/ignore/IgnoreRule.java
index 42bbd9e9b8..f14d1bd0b2 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/ignore/IgnoreRule.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/ignore/IgnoreRule.java
@@ -46,11 +46,16 @@ import org.eclipse.jgit.errors.InvalidPatternException;
 import org.eclipse.jgit.fnmatch.FileNameMatcher;
 
 /**
- * A single ignore rule corresponding to one line in a .gitignore or
- * ignore file. Parses the ignore pattern
+ * A single ignore rule corresponding to one line in a .gitignore or ignore
+ * file. Parses the ignore pattern
  *
  * Inspiration from: Ferry Huberts
+ *
+ * @deprecated this rule does not support double star pattern and is slow
+ *             parsing glob expressions. Consider to use {@link FastIgnoreRule}
+ *             instead. See https://bugs.eclipse.org/bugs/show_bug.cgi?id=440732
  */
+@Deprecated
 public class IgnoreRule {
 	private String pattern;
 	private boolean negation;
@@ -270,4 +275,4 @@ public class IgnoreRule {
 	public String toString() {
 		return pattern;
 	}
-}
\ No newline at end of file
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/ignore/internal/AbstractMatcher.java b/org.eclipse.jgit/src/org/eclipse/jgit/ignore/internal/AbstractMatcher.java
new file mode 100644
index 0000000000..4e90d8c3cb
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/ignore/internal/AbstractMatcher.java
@@ -0,0 +1,88 @@
+/*
+ * Copyright (C) 2014, Andrey Loskutov <loskutov@gmx.de>
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+package org.eclipse.jgit.ignore.internal;
+
+/**
+ * Base class for default methods as {@link #toString()} and such.
+ * <p>
+ * This class is immutable and thread safe.
+ *
+ * @since 3.6
+ */
+public abstract class AbstractMatcher implements IMatcher {
+
+	final boolean dirOnly;
+
+	final String pattern;
+
+	/**
+	 * @param pattern
+	 *            string to parse
+	 * @param dirOnly
+	 *            true if this matcher should match only directories
+	 */
+	AbstractMatcher(String pattern, boolean dirOnly) {
+		this.pattern = pattern;
+		this.dirOnly = dirOnly;
+	}
+
+	@Override
+	public String toString() {
+		return pattern;
+	}
+
+	@Override
+	public int hashCode() {
+		return pattern.hashCode();
+	}
+
+	@Override
+	public boolean equals(Object obj) {
+		if (this == obj)
+			return true;
+		if (!(obj instanceof AbstractMatcher))
+			return false;
+		AbstractMatcher other = (AbstractMatcher) obj;
+		return dirOnly == other.dirOnly && pattern.equals(other.pattern);
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/ignore/internal/IMatcher.java b/org.eclipse.jgit/src/org/eclipse/jgit/ignore/internal/IMatcher.java
new file mode 100644
index 0000000000..10b5e49e1f
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/ignore/internal/IMatcher.java
@@ -0,0 +1,80 @@
+/*
+ * Copyright (C) 2014, Andrey Loskutov <loskutov@gmx.de>
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+package org.eclipse.jgit.ignore.internal;
+
+/**
+ * Generic string matcher
+ *
+ * @since 3.6
+ */
+public interface IMatcher {
+
+	/**
+	 * Matches entire given string
+	 *
+	 * @param path
+	 *            string which is not null, but might be empty
+	 * @param assumeDirectory
+	 *            true to assume this path as directory (even if it doesn't end
+	 *            with a slash)
+	 * @return true if this matcher pattern matches given string
+	 */
+	boolean matches(String path, boolean assumeDirectory);
+
+	/**
+	 * Matches only part of given string
+	 *
+	 * @param segment
+	 *            string which is not null, but might be empty
+	 * @param startIncl
+	 *            start index, inclusive
+	 * @param endExcl
+	 *            end index, exclusive
+	 * @param assumeDirectory
+	 *            true to assume this path as directory (even if it doesn't end
+	 *            with a slash)
+	 * @return true if this matcher pattern matches given string
+	 */
+	boolean matches(String segment, int startIncl, int endExcl,
+			boolean assumeDirectory);
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/ignore/internal/NameMatcher.java b/org.eclipse.jgit/src/org/eclipse/jgit/ignore/internal/NameMatcher.java
new file mode 100644
index 0000000000..6c4c8092fe
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/ignore/internal/NameMatcher.java
@@ -0,0 +1,112 @@
+/*
+ * Copyright (C) 2014, Andrey Loskutov <loskutov@gmx.de>
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+package org.eclipse.jgit.ignore.internal;
+
+import static org.eclipse.jgit.ignore.internal.Strings.getPathSeparator;
+
+/**
+ * Matcher built from patterns for file names (single path segments). This class
+ * is immutable and thread safe.
+ *
+ * @since 3.6
+ */
+public class NameMatcher extends AbstractMatcher {
+
+	final boolean beginning;
+
+	final char slash;
+
+	final String subPattern;
+
+	NameMatcher(String pattern, Character pathSeparator, boolean dirOnly) {
+		super(pattern, dirOnly);
+		slash = getPathSeparator(pathSeparator);
+		beginning = pattern.length() == 0 ? false : pattern.charAt(0) == slash;
+		if (!beginning)
+			this.subPattern = pattern;
+		else
+			this.subPattern = pattern.substring(1);
+	}
+
+	public boolean matches(String path, boolean assumeDirectory) {
+		int end = 0;
+		int firstChar = 0;
+		do {
+			firstChar = getFirstNotSlash(path, end);
+			end = getFirstSlash(path, firstChar);
+			boolean match = matches(path, firstChar, end, assumeDirectory);
+			if (match)
+				// make sure the directory matches: either if we are done with
+				// segment and there is next one, or if the directory is assumed
+				return !dirOnly ? true : (end > 0 && end != path.length())
+						|| assumeDirectory;
+		} while (!beginning && end != path.length());
+		return false;
+	}
+
+	public boolean matches(String segment, int startIncl, int endExcl,
+			boolean assumeDirectory) {
+		// faster local access, same as in string.indexOf()
+		String s = subPattern;
+		if (s.length() != (endExcl - startIncl))
+			return false;
+		for (int i = 0; i < s.length(); i++) {
+			char c1 = s.charAt(i);
+			char c2 = segment.charAt(i + startIncl);
+			if (c1 != c2)
+				return false;
+		}
+		return true;
+	}
+
+	private int getFirstNotSlash(String s, int start) {
+		int slashIdx = s.indexOf(slash, start);
+		return slashIdx == start ? start + 1 : start;
+	}
+
+	private int getFirstSlash(String s, int start) {
+		int slashIdx = s.indexOf(slash, start);
+		return slashIdx == -1 ? s.length() : slashIdx;
+	}
+
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/ignore/internal/PathMatcher.java b/org.eclipse.jgit/src/org/eclipse/jgit/ignore/internal/PathMatcher.java
new file mode 100644
index 0000000000..753971ed40
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/ignore/internal/PathMatcher.java
@@ -0,0 +1,239 @@
+/*
+ * Copyright (C) 2014, Andrey Loskutov <loskutov@gmx.de>
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+package org.eclipse.jgit.ignore.internal;
+
+import static org.eclipse.jgit.ignore.internal.Strings.*;
+
+import java.util.*;
+
+import org.eclipse.jgit.errors.InvalidPatternException;
+import org.eclipse.jgit.ignore.FastIgnoreRule;
+
+/**
+ * Matcher built by patterns consists of multiple path segments.
+ * <p>
+ * This class is immutable and thread safe.
+ *
+ * @since 3.6
+ */
+public class PathMatcher extends AbstractMatcher {
+
+	private static final WildMatcher WILD = WildMatcher.INSTANCE;
+
+	private final List<IMatcher> matchers;
+
+	private final char slash;
+
+	private boolean beginning;
+
+	PathMatcher(String pattern, Character pathSeparator, boolean dirOnly)
+			throws InvalidPatternException {
+		super(pattern, dirOnly);
+		slash = getPathSeparator(pathSeparator);
+		beginning = pattern.indexOf(slash) == 0;
+		if (isSimplePathWithSegments(pattern))
+			matchers = null;
+		else
+			matchers = createMatchers(split(pattern, slash), pathSeparator,
+					dirOnly);
+	}
+
+	private boolean isSimplePathWithSegments(String path) {
+		return !isWildCard(path) && count(path, slash, true) > 0;
+	}
+
+	static private List<IMatcher> createMatchers(List<String> segments,
+			Character pathSeparator, boolean dirOnly)
+			throws InvalidPatternException {
+		List<IMatcher> matchers = new ArrayList<IMatcher>(segments.size());
+		for (int i = 0; i < segments.size(); i++) {
+			String segment = segments.get(i);
+			IMatcher matcher = createNameMatcher0(segment, pathSeparator,
+					dirOnly);
+			if (matcher == WILD && i > 0
+					&& matchers.get(matchers.size() - 1) == WILD)
+				// collapse wildmatchers **/** is same as **
+				continue;
+			matchers.add(matcher);
+		}
+		return matchers;
+	}
+
+	/**
+	 *
+	 * @param pattern
+	 * @param pathSeparator
+	 *            if this parameter isn't null then this character will not
+	 *            match at wildcards(* and ? are wildcards).
+	 * @param dirOnly
+	 * @return never null
+	 * @throws InvalidPatternException
+	 */
+	public static IMatcher createPathMatcher(String pattern,
+			Character pathSeparator, boolean dirOnly)
+			throws InvalidPatternException {
+		pattern = pattern.trim();
+		char slash = Strings.getPathSeparator(pathSeparator);
+		// ignore possible leading and trailing slash
+		int slashIdx = pattern.indexOf(slash, 1);
+		if (slashIdx > 0 && slashIdx < pattern.length() - 1)
+			return new PathMatcher(pattern, pathSeparator, dirOnly);
+		return createNameMatcher0(pattern, pathSeparator, dirOnly);
+	}
+
+	private static IMatcher createNameMatcher0(String segment,
+			Character pathSeparator, boolean dirOnly)
+			throws InvalidPatternException {
+		// check if we see /** or ** segments => double star pattern
+		if (WildMatcher.WILDMATCH.equals(segment)
+				|| WildMatcher.WILDMATCH2.equals(segment))
+			return WILD;
+		if (isWildCard(segment))
+			return new WildCardMatcher(segment, pathSeparator, dirOnly);
+		return new NameMatcher(segment, pathSeparator, dirOnly);
+	}
+
+	public boolean matches(String path, boolean assumeDirectory) {
+		if (matchers == null)
+			return simpleMatch(path, assumeDirectory);
+		return iterate(path, 0, path.length(), assumeDirectory);
+	}
+
+	/*
+	 * Stupid but fast string comparison: the case where we don't have to match
+	 * wildcards or single segments (mean: this is multi-segment path which must
+	 * be at the beginning of the another string)
+	 */
+	private boolean simpleMatch(String path, boolean assumeDirectory) {
+		boolean hasSlash = path.indexOf(slash) == 0;
+		if (beginning && !hasSlash)
+			path = slash + path;
+
+		if (!beginning && hasSlash)
+			path = path.substring(1);
+
+		if (path.equals(pattern))
+			// Exact match
+			if (dirOnly && !assumeDirectory)
+				// Directory expectations not met
+				return false;
+			else
+				// Directory expectations met
+				return true;
+
+		/*
+		 * Add slashes for startsWith check. This avoids matching e.g.
+		 * "/src/new" to /src/newfile" but allows "/src/new" to match
+		 * "/src/new/newfile", as is the git standard
+		 */
+		if (path.startsWith(pattern + FastIgnoreRule.PATH_SEPARATOR))
+			return true;
+
+		return false;
+	}
+
+	public boolean matches(String segment, int startIncl, int endExcl,
+			boolean assumeDirectory) {
+		throw new UnsupportedOperationException(
+				"Path matcher works only on entire paths"); //$NON-NLS-1$
+	}
+
+	boolean iterate(final String path, final int startIncl, final int endExcl,
+			boolean assumeDirectory) {
+		int matcher = 0;
+		int right = startIncl;
+		boolean match = false;
+		int lastWildmatch = -1;
+		while (true) {
+			int left = right;
+			right = path.indexOf(slash, right);
+			if (right == -1) {
+				if (left < endExcl)
+					match = matches(matcher, path, left, endExcl,
+							assumeDirectory);
+				if (match) {
+					if (matcher == matchers.size() - 2
+							&& matchers.get(matcher + 1) == WILD)
+						// ** can match *nothing*: a/b/** match also a/b
+						return true;
+					if (matcher < matchers.size() - 1
+							&& matchers.get(matcher) == WILD) {
+						// ** can match *nothing*: a/**/b match also a/b
+						matcher++;
+						match = matches(matcher, path, left, endExcl,
+								assumeDirectory);
+					} else if (dirOnly)
+						return false;
+				}
+				return match && matcher + 1 == matchers.size();
+			}
+			if (right - left > 0)
+				match = matches(matcher, path, left, right, assumeDirectory);
+			else {
+				// path starts with slash???
+				right++;
+				continue;
+			}
+			if (match) {
+				if (matchers.get(matcher) == WILD) {
+					lastWildmatch = matcher;
+					// ** can match *nothing*: a/**/b match also a/b
+					right = left - 1;
+				}
+				matcher++;
+				if (matcher == matchers.size())
+					return true;
+			} else if (lastWildmatch != -1)
+				matcher = lastWildmatch + 1;
+			else
+				return false;
+			right++;
+		}
+	}
+
+	boolean matches(int matcherIdx, String path, int startIncl, int endExcl,
+			boolean assumeDirectory) {
+		IMatcher matcher = matchers.get(matcherIdx);
+		return matcher.matches(path, startIncl, endExcl, assumeDirectory);
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/ignore/internal/Strings.java b/org.eclipse.jgit/src/org/eclipse/jgit/ignore/internal/Strings.java
new file mode 100644
index 0000000000..e9b300760a
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/ignore/internal/Strings.java
@@ -0,0 +1,373 @@
+/*
+ * Copyright (C) 2014, Andrey Loskutov <loskutov@gmx.de>
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+package org.eclipse.jgit.ignore.internal;
+
+import static java.lang.Character.isLetter;
+
+import java.util.*;
+import java.util.regex.Pattern;
+
+import org.eclipse.jgit.errors.InvalidPatternException;
+import org.eclipse.jgit.ignore.FastIgnoreRule;
+
+/**
+ * Various {@link String} related utility methods, written mostly to avoid
+ * generation of new String objects (e.g. via splitting Strings etc).
+ *
+ * @since 3.6
+ */
+public class Strings {
+
+	static char getPathSeparator(Character pathSeparator) {
+		return pathSeparator == null ? FastIgnoreRule.PATH_SEPARATOR
+				: pathSeparator.charValue();
+	}
+
+	/**
+	 * @param pattern
+	 *            non null
+	 * @param c
+	 *            character to remove
+	 * @return new string with all trailing characters removed
+	 */
+	public static String stripTrailing(String pattern, char c) {
+		while (pattern.length() > 0
+				&& pattern.charAt(pattern.length() - 1) == c)
+			pattern = pattern.substring(0, pattern.length() - 1);
+		return pattern;
+	}
+
+	static int count(String s, char c, boolean ignoreFirstLast) {
+		int start = 0;
+		int count = 0;
+		while (true) {
+			start = s.indexOf(c, start);
+			if (start == -1)
+				break;
+			if (!ignoreFirstLast || (start != 0 && start != s.length()))
+				count++;
+			start++;
+		}
+		return count;
+	}
+
+	/**
+	 * Splits given string to substrings by given separator
+	 *
+	 * @param pattern
+	 *            non null
+	 * @param slash
+	 *            separator char
+	 * @return list of substrings
+	 */
+	public static List<String> split(String pattern, char slash) {
+		int count = count(pattern, slash, true);
+		if (count < 1)
+			throw new IllegalStateException(
+					"Pattern must have at least two segments: " + pattern); //$NON-NLS-1$
+		List<String> segments = new ArrayList<String>(count);
+		int right = 0;
+		while (true) {
+			int left = right;
+			right = pattern.indexOf(slash, right);
+			if (right == -1) {
+				if (left < pattern.length())
+					segments.add(pattern.substring(left));
+				break;
+			}
+			if (right - left > 0)
+				if (left == 1)
+					// leading slash should remain by the first pattern
+					segments.add(pattern.substring(left - 1, right));
+				else if (right == pattern.length() - 1)
+					// trailing slash should remain too
+					segments.add(pattern.substring(left, right + 1));
+				else
+					segments.add(pattern.substring(left, right));
+			right++;
+		}
+		return segments;
+	}
+
+	static boolean isWildCard(String pattern) {
+		return pattern.indexOf('*') != -1 || pattern.indexOf('?') != -1
+				|| pattern.indexOf('[') != -1
+				// required to match escaped backslashes '\\\\'
+				|| pattern.indexOf('\\') != -1 || pattern.indexOf(']') != -1;
+	}
+
+	final static List<String> POSIX_CHAR_CLASSES = Arrays.asList(
+			"alnum", "alpha", "blank", "cntrl", //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
+			// [:alnum:] [:alpha:] [:blank:] [:cntrl:]
+			"digit", "graph", "lower", "print", //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
+			// [:digit:] [:graph:] [:lower:] [:print:]
+			"punct", "space", "upper", "xdigit", //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
+			// [:punct:] [:space:] [:upper:] [:xdigit:]
+			"word" //$NON-NLS-1$
+	// [:word:] XXX I don't see it in
+	// http://man7.org/linux/man-pages/man7/glob.7.html
+	// but this was in org.eclipse.jgit.fnmatch.GroupHead.java ???
+			);
+
+	private static final String DL = "\\p{javaDigit}\\p{javaLetter}"; //$NON-NLS-1$
+
+	final static List<String> JAVA_CHAR_CLASSES = Arrays
+			.asList("\\p{Alnum}", "\\p{javaLetter}", "\\p{Blank}", "\\p{Cntrl}", //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
+					// [:alnum:] [:alpha:] [:blank:] [:cntrl:]
+					"\\p{javaDigit}", "[\\p{Graph}" + DL + "]", "\\p{Ll}", "[\\p{Print}" + DL + "]", //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$ //$NON-NLS-5$ //$NON-NLS-6$
+					// [:digit:] [:graph:] [:lower:] [:print:]
+					"\\p{Punct}", "\\p{Space}", "\\p{Lu}", "\\p{XDigit}", //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
+					// [:punct:] [:space:] [:upper:] [:xdigit:]
+					"[" + DL + "_]" //$NON-NLS-1$ //$NON-NLS-2$
+							// [:word:]
+			);
+
+	// Collating symbols [[.a.]] or equivalence class expressions [[=a=]] are
+	// not supported by CLI git (at least not by 1.9.1)
+	final static Pattern UNSUPPORTED = Pattern
+			.compile("\\[\\[[.=]\\w+[.=]\\]\\]"); //$NON-NLS-1$
+
+	/**
+	 * Conversion from glob to Java regex following two sources: <li>
+	 * http://man7.org/linux/man-pages/man7/glob.7.html <li>
+	 * org.eclipse.jgit.fnmatch.FileNameMatcher.java Seems that there are
+	 * various ways to define what "glob" can be.
+	 *
+	 * @param pattern
+	 *            non null pattern
+	 *
+	 * @return Java regex pattern corresponding to given glob pattern
+	 * @throws InvalidPatternException
+	 */
+	static Pattern convertGlob(String pattern) throws InvalidPatternException {
+		if (UNSUPPORTED.matcher(pattern).find())
+			throw new InvalidPatternException(
+					"Collating symbols [[.a.]] or equivalence class expressions [[=a=]] are not supported", //$NON-NLS-1$
+					pattern);
+
+		StringBuilder sb = new StringBuilder(pattern.length());
+
+		int in_brackets = 0;
+		boolean seenEscape = false;
+		boolean ignoreLastBracket = false;
+		boolean in_char_class = false;
+		// 6 is the length of the longest posix char class "xdigit"
+		char[] charClass = new char[6];
+
+		for (int i = 0; i < pattern.length(); i++) {
+			char c = pattern.charAt(i);
+			switch (c) {
+
+			case '*':
+				if (seenEscape || in_brackets > 0)
+					sb.append(c);
+				else
+					sb.append('.').append(c);
+				break;
+
+			case '.':
+				if (seenEscape)
+					sb.append(c);
+				else
+					sb.append('\\').append('.');
+				break;
+
+			case '?':
+				if (seenEscape || in_brackets > 0)
+					sb.append(c);
+				else
+					sb.append('.');
+				break;
+
+			case ':':
+				if (in_brackets > 0)
+					if (lookBehind(sb) == '['
+							&& isLetter(lookAhead(pattern, i)))
+						in_char_class = true;
+				sb.append(':');
+				break;
+
+			case '-':
+				if (in_brackets > 0) {
+					if (lookAhead(pattern, i) == ']')
+						sb.append('\\').append(c);
+					else
+						sb.append(c);
+				} else
+					sb.append('-');
+				break;
+
+			case '\\':
+				if (in_brackets > 0) {
+					char lookAhead = lookAhead(pattern, i);
+					if (lookAhead == ']' || lookAhead == '[')
+						ignoreLastBracket = true;
+				}
+				sb.append(c);
+				break;
+
+			case '[':
+				if (in_brackets > 0) {
+					sb.append('\\').append('[');
+					ignoreLastBracket = true;
+				} else {
+					if (!seenEscape) {
+						in_brackets++;
+						ignoreLastBracket = false;
+					}
+					sb.append('[');
+				}
+				break;
+
+			case ']':
+				if (seenEscape) {
+					sb.append(']');
+					ignoreLastBracket = true;
+					break;
+				}
+				if (in_brackets <= 0) {
+					sb.append('\\').append(']');
+					ignoreLastBracket = true;
+					break;
+				}
+				char lookBehind = lookBehind(sb);
+				if ((lookBehind == '[' && !ignoreLastBracket)
+						|| lookBehind == '^') {
+					sb.append('\\');
+					sb.append(']');
+					ignoreLastBracket = true;
+				} else {
+					ignoreLastBracket = false;
+					if (!in_char_class) {
+						in_brackets--;
+						sb.append(']');
+					} else {
+						in_char_class = false;
+						String charCl = checkPosixCharClass(charClass);
+						// delete last \[:: chars and set the pattern
+						if (charCl != null) {
+							sb.setLength(sb.length() - 4);
+							sb.append(charCl);
+						}
+						reset(charClass);
+					}
+				}
+				break;
+
+			case '!':
+				if (in_brackets > 0) {
+					if (lookBehind(sb) == '[')
+						sb.append('^');
+					else
+						sb.append(c);
+				} else
+					sb.append(c);
+				break;
+
+			default:
+				if (in_char_class)
+					setNext(charClass, c);
+				else
+					sb.append(c);
+				break;
+			} // end switch
+
+			seenEscape = c == '\\';
+
+		} // end for
+
+		if (in_brackets > 0)
+			throw new InvalidPatternException("Not closed bracket?", pattern); //$NON-NLS-1$
+		return Pattern.compile(sb.toString());
+	}
+
+	/**
+	 * @param buffer
+	 * @return zero of the buffer is empty, otherwise the last character from
+	 *         buffer
+	 */
+	private static char lookBehind(StringBuilder buffer) {
+		return buffer.length() > 0 ? buffer.charAt(buffer.length() - 1) : 0;
+	}
+
+	/**
+	 * @param pattern
+	 * @param i
+	 *            current pointer in the pattern
+	 * @return zero of the index is out of range, otherwise the next character
+	 *         from given position
+	 */
+	private static char lookAhead(String pattern, int i) {
+		int idx = i + 1;
+		return idx >= pattern.length() ? 0 : pattern.charAt(idx);
+	}
+
+	private static void setNext(char[] buffer, char c) {
+		for (int i = 0; i < buffer.length; i++)
+			if (buffer[i] == 0) {
+				buffer[i] = c;
+				break;
+			}
+	}
+
+	private static void reset(char[] buffer) {
+		for (int i = 0; i < buffer.length; i++)
+			buffer[i] = 0;
+	}
+
+	private static String checkPosixCharClass(char[] buffer) {
+		for (int i = 0; i < POSIX_CHAR_CLASSES.size(); i++) {
+			String clazz = POSIX_CHAR_CLASSES.get(i);
+			boolean match = true;
+			for (int j = 0; j < clazz.length(); j++)
+				if (buffer[j] != clazz.charAt(j)) {
+					match = false;
+					break;
+				}
+			if (match)
+				return JAVA_CHAR_CLASSES.get(i);
+		}
+		return null;
+	}
+
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/ignore/internal/WildCardMatcher.java b/org.eclipse.jgit/src/org/eclipse/jgit/ignore/internal/WildCardMatcher.java
new file mode 100644
index 0000000000..7d12b0ddce
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/ignore/internal/WildCardMatcher.java
@@ -0,0 +1,74 @@
+/*
+ * Copyright (C) 2014, Andrey Loskutov <loskutov@gmx.de>
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+package org.eclipse.jgit.ignore.internal;
+
+import static org.eclipse.jgit.ignore.internal.Strings.convertGlob;
+
+import java.util.regex.Pattern;
+
+import org.eclipse.jgit.errors.InvalidPatternException;
+
+/**
+ * Matcher built from path segments containing wildcards. This matcher converts
+ * glob wildcards to Java {@link Pattern}'s.
+ * <p>
+ * This class is immutable and thread safe.
+ *
+ * @since 3.6
+ */
+public class WildCardMatcher extends NameMatcher {
+
+	final Pattern p;
+
+	WildCardMatcher(String pattern, Character pathSeparator, boolean dirOnly)
+			throws InvalidPatternException {
+		super(pattern, pathSeparator, dirOnly);
+		p = convertGlob(subPattern);
+	}
+
+	@Override
+	public boolean matches(String segment, int startIncl, int endExcl,
+			boolean assumeDirectory) {
+		return p.matcher(segment.substring(startIncl, endExcl)).matches();
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/ignore/internal/WildMatcher.java b/org.eclipse.jgit/src/org/eclipse/jgit/ignore/internal/WildMatcher.java
new file mode 100644
index 0000000000..d578654375
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/ignore/internal/WildMatcher.java
@@ -0,0 +1,75 @@
+/*
+ * Copyright (C) 2014, Andrey Loskutov <loskutov@gmx.de>
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+package org.eclipse.jgit.ignore.internal;
+
+/**
+ * Wildmatch matcher for "double star" (<code>**</code>) pattern only. This
+ * matcher matches any path.
+ * <p>
+ * This class is immutable and thread safe.
+ *
+ * @since 3.6
+ */
+public final class WildMatcher extends AbstractMatcher {
+
+	static final String WILDMATCH = "**"; //$NON-NLS-1$
+
+	// double star for the beginning of pattern
+	static final String WILDMATCH2 = "/**"; //$NON-NLS-1$
+
+	static final WildMatcher INSTANCE = new WildMatcher();
+
+	private WildMatcher() {
+		super(WILDMATCH, false);
+	}
+
+	public final boolean matches(String path, boolean assumeDirectory) {
+		return true;
+	}
+
+	public final boolean matches(String segment, int startIncl, int endExcl,
+			boolean assumeDirectory) {
+		return true;
+	}
+
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/WorkingTreeIterator.java b/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/WorkingTreeIterator.java
index 3d63d92542..cc5ef18074 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/WorkingTreeIterator.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/WorkingTreeIterator.java
@@ -70,8 +70,8 @@ import org.eclipse.jgit.dircache.DirCacheIterator;
 import org.eclipse.jgit.errors.CorruptObjectException;
 import org.eclipse.jgit.errors.MissingObjectException;
 import org.eclipse.jgit.errors.NoWorkTreeException;
+import org.eclipse.jgit.ignore.FastIgnoreRule;
 import org.eclipse.jgit.ignore.IgnoreNode;
-import org.eclipse.jgit.ignore.IgnoreRule;
 import org.eclipse.jgit.internal.JGitText;
 import org.eclipse.jgit.lib.Constants;
 import org.eclipse.jgit.lib.CoreConfig;
@@ -1132,7 +1132,7 @@ public abstract class WorkingTreeIterator extends AbstractTreeIterator {
 		final Entry entry;
 
 		PerDirectoryIgnoreNode(Entry entry) {
-			super(Collections.<IgnoreRule> emptyList());
+			super(Collections.<FastIgnoreRule> emptyList());
 			this.entry = entry;
 		}