FileNameMatcher

/*
 * Copyright (C) 2008, Florian Koeberle <florianskarten@web.de>
 * Copyright (C) 2008, Florian Köberle <florianskarten@web.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.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(final 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<Head>(heads.size());
		this.heads.addAll(heads);
		this.listForLocalUseage = new ArrayList<Head>(heads.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));
	}

	/**
	 * A Copy Constructor which creates a new {@link FileNameMatcher} with the
	 * same state and reset point like <code>other</code>.
	 *
	 * @param other
	 *            another {@link 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<Head>(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<Head>(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<AbstractHead>();
		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<AbstractHead>(
				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);
		else
			return new WildCardHead(star);
	}

	/**
	 * @param c new character to append
	 * @return true to continue, false if the matcher can stop appending
	 */
	private boolean 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) {
				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;
	}

	/**
	 *
	 * @param stringToMatch
	 *            extends the string which is matched against the patterns of
	 *            this class.
	 */
	public void append(final 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);
	}

	/**
	 *
	 * @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);
	}

	/**
	 *
	 * @return true, if the string currently being matched does match.
	 */
	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;
	}

	/**
	 *
	 * @return false, if the string being matched will not match when the string
	 *         gets extended.
	 */
	public boolean canAppendMatch() {
		for (int i = 0; i < heads.size(); i++) {
			if (heads.get(i) != LastHead.INSTANCE) {
				return true;
			}
		}
		return false;
	}
}