TreeWalk.java

/*
 * Copyright (C) 2008, 2009 Google Inc.
 * Copyright (C) 2008, 2022 Shawn O. Pearce <spearce@spearce.org> 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.treewalk;

import static java.nio.charset.StandardCharsets.UTF_8;

import java.io.IOException;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.regex.Matcher;

import org.eclipse.jgit.annotations.Nullable;
import org.eclipse.jgit.api.errors.JGitInternalException;
import org.eclipse.jgit.attributes.Attribute;
import org.eclipse.jgit.attributes.Attributes;
import org.eclipse.jgit.attributes.AttributesHandler;
import org.eclipse.jgit.attributes.AttributesNodeProvider;
import org.eclipse.jgit.attributes.AttributesProvider;
import org.eclipse.jgit.attributes.FilterCommandRegistry;
import org.eclipse.jgit.dircache.DirCacheBuildIterator;
import org.eclipse.jgit.dircache.DirCacheIterator;
import org.eclipse.jgit.errors.CorruptObjectException;
import org.eclipse.jgit.errors.IncorrectObjectTypeException;
import org.eclipse.jgit.errors.MissingObjectException;
import org.eclipse.jgit.errors.StopWalkException;
import org.eclipse.jgit.lib.AnyObjectId;
import org.eclipse.jgit.lib.Config;
import org.eclipse.jgit.lib.ConfigConstants;
import org.eclipse.jgit.lib.Constants;
import org.eclipse.jgit.lib.CoreConfig.EolStreamType;
import org.eclipse.jgit.lib.FileMode;
import org.eclipse.jgit.lib.MutableObjectId;
import org.eclipse.jgit.lib.ObjectId;
import org.eclipse.jgit.lib.ObjectReader;
import org.eclipse.jgit.lib.Repository;
import org.eclipse.jgit.revwalk.RevTree;
import org.eclipse.jgit.treewalk.filter.PathFilter;
import org.eclipse.jgit.treewalk.filter.TreeFilter;
import org.eclipse.jgit.util.QuotedString;
import org.eclipse.jgit.util.RawParseUtils;
import org.eclipse.jgit.util.io.EolStreamTypeUtil;

/**
 * Walks one or more {@link org.eclipse.jgit.treewalk.AbstractTreeIterator}s in
 * parallel.
 * <p>
 * This class can perform n-way differences across as many trees as necessary.
 * <p>
 * Each tree added must have the same root as existing trees in the walk.
 * <p>
 * A TreeWalk instance can only be used once to generate results. Running a
 * second time requires creating a new TreeWalk instance, or invoking
 * {@link #reset()} and adding new trees before starting again. Resetting an
 * existing instance may be faster for some applications as some internal
 * buffers may be recycled.
 * <p>
 * TreeWalk instances are not thread-safe. Applications must either restrict
 * usage of a TreeWalk instance to a single thread, or implement their own
 * synchronization at a higher level.
 * <p>
 * Multiple simultaneous TreeWalk instances per
 * {@link org.eclipse.jgit.lib.Repository} are permitted, even from concurrent
 * threads.
 */
public class TreeWalk implements AutoCloseable, AttributesProvider {

    private static final AbstractTreeIterator[] NO_TREES = {};

    /**
     * @since 4.2
     */
    public enum OperationType {
        /**
         * Represents a checkout operation (for example a checkout or reset
         * operation).
         */
        CHECKOUT_OP,

        /**
         * Represents a checkin operation (for example an add operation)
         */
        CHECKIN_OP
    }

    /**
     * Type of operation you want to retrieve the git attributes for.
     */
    private OperationType operationType = OperationType.CHECKOUT_OP;

    /**
     * The filter command as defined in gitattributes. The keys are
     * filterName+"."+filterCommandType. E.g. "lfs.clean"
     */
    private Map<String, String> filterCommandsByNameDotType = new HashMap<>();

    /**
     * Set the operation type of this walk
     *
     * @param operationType
     *            a {@link org.eclipse.jgit.treewalk.TreeWalk.OperationType}
     *            object.
     * @since 4.2
     */
    public void setOperationType(OperationType operationType) {
        this.operationType = operationType;
    }

    /**
     * Open a tree walk and filter to exactly one path.
     * <p>
     * The returned tree walk is already positioned on the requested path, so
     * the caller should not need to invoke {@link #next()} unless they are
     * looking for a possible directory/file name conflict.
     *
     * @param reader
     *            the reader the walker will obtain tree data from.
     * @param path
     *            single path to advance the tree walk instance into.
     * @param trees
     *            one or more trees to walk through, all with the same root.
     * @return a new tree walk configured for exactly this one path; null if no
     *         path was found in any of the trees.
     * @throws java.io.IOException
     *             reading a pack file or loose object failed.
     * @throws org.eclipse.jgit.errors.CorruptObjectException
     *             an tree object could not be read as its data stream did not
     *             appear to be a tree, or could not be inflated.
     * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
     *             an object we expected to be a tree was not a tree.
     * @throws org.eclipse.jgit.errors.MissingObjectException
     *             a tree object was not found.
     */
    public static TreeWalk forPath(final ObjectReader reader, final String path,
            final AnyObjectId... trees) throws MissingObjectException,
            IncorrectObjectTypeException, CorruptObjectException, IOException {
        return forPath(null, reader, path, trees);
    }

    /**
     * Open a tree walk and filter to exactly one path.
     * <p>
     * The returned tree walk is already positioned on the requested path, so
     * the caller should not need to invoke {@link #next()} unless they are
     * looking for a possible directory/file name conflict.
     *
     * @param repo
     *            repository to read config data and
     *            {@link org.eclipse.jgit.attributes.AttributesNodeProvider}
     *            from.
     * @param reader
     *            the reader the walker will obtain tree data from.
     * @param path
     *            single path to advance the tree walk instance into.
     * @param trees
     *            one or more trees to walk through, all with the same root.
     * @return a new tree walk configured for exactly this one path; null if no
     *         path was found in any of the trees.
     * @throws java.io.IOException
     *             reading a pack file or loose object failed.
     * @throws org.eclipse.jgit.errors.CorruptObjectException
     *             an tree object could not be read as its data stream did not
     *             appear to be a tree, or could not be inflated.
     * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
     *             an object we expected to be a tree was not a tree.
     * @throws org.eclipse.jgit.errors.MissingObjectException
     *             a tree object was not found.
     * @since 4.3
     */
    public static TreeWalk forPath(final @Nullable Repository repo,
            final ObjectReader reader, final String path,
            final AnyObjectId... trees)
                    throws MissingObjectException, IncorrectObjectTypeException,
                    CorruptObjectException, IOException {
        TreeWalk tw = new TreeWalk(repo, reader);
        PathFilter f = PathFilter.create(path);
        tw.setFilter(f);
        tw.reset(trees);
        tw.setRecursive(false);

        while (tw.next()) {
            if (f.isDone(tw)) {
                return tw;
            } else if (tw.isSubtree()) {
                tw.enterSubtree();
            }
        }
        return null;
    }

    /**
     * Open a tree walk and filter to exactly one path.
     * <p>
     * The returned tree walk is already positioned on the requested path, so
     * the caller should not need to invoke {@link #next()} unless they are
     * looking for a possible directory/file name conflict.
     *
     * @param db
     *            repository to read tree object data from.
     * @param path
     *            single path to advance the tree walk instance into.
     * @param trees
     *            one or more trees to walk through, all with the same root.
     * @return a new tree walk configured for exactly this one path; null if no
     *         path was found in any of the trees.
     * @throws java.io.IOException
     *             reading a pack file or loose object failed.
     * @throws org.eclipse.jgit.errors.CorruptObjectException
     *             an tree object could not be read as its data stream did not
     *             appear to be a tree, or could not be inflated.
     * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
     *             an object we expected to be a tree was not a tree.
     * @throws org.eclipse.jgit.errors.MissingObjectException
     *             a tree object was not found.
     */
    public static TreeWalk forPath(final Repository db, final String path,
            final AnyObjectId... trees) throws MissingObjectException,
            IncorrectObjectTypeException, CorruptObjectException, IOException {
        try (ObjectReader reader = db.newObjectReader()) {
            return forPath(db, reader, path, trees);
        }
    }

    /**
     * Open a tree walk and filter to exactly one path.
     * <p>
     * The returned tree walk is already positioned on the requested path, so
     * the caller should not need to invoke {@link #next()} unless they are
     * looking for a possible directory/file name conflict.
     *
     * @param db
     *            repository to read tree object data from.
     * @param path
     *            single path to advance the tree walk instance into.
     * @param tree
     *            the single tree to walk through.
     * @return a new tree walk configured for exactly this one path; null if no
     *         path was found in any of the trees.
     * @throws java.io.IOException
     *             reading a pack file or loose object failed.
     * @throws org.eclipse.jgit.errors.CorruptObjectException
     *             an tree object could not be read as its data stream did not
     *             appear to be a tree, or could not be inflated.
     * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
     *             an object we expected to be a tree was not a tree.
     * @throws org.eclipse.jgit.errors.MissingObjectException
     *             a tree object was not found.
     */
    public static TreeWalk forPath(final Repository db, final String path,
            final RevTree tree) throws MissingObjectException,
            IncorrectObjectTypeException, CorruptObjectException, IOException {
        return forPath(db, path, new ObjectId[] { tree });
    }

    private final ObjectReader reader;

    private final boolean closeReader;

    private final MutableObjectId idBuffer = new MutableObjectId();

    private TreeFilter filter;

    AbstractTreeIterator[] trees;

    private boolean recursive;

    private boolean postOrderTraversal;

    int depth;

    private boolean advance;

    private boolean postChildren;

    private AttributesNodeProvider attributesNodeProvider;

    AbstractTreeIterator currentHead;

    /**
     * Cached attributes for the current entry; per tree. Index i+1 is for tree
     * i; index 0 is for the deprecated legacy behavior.
     */
    private Attributes[] attrs;

    /**
     * Cached attributes handler; per tree. Index i+1 is for tree i; index 0 is
     * for the deprecated legacy behavior.
     */
    private AttributesHandler[] attributesHandlers;

    /** Can be set to identify the tree to use for {@link #getAttributes()}. */
    private int headIndex = -1;

    private Config config;

    private Set<String> filterCommands;

    /**
     * Create a new tree walker for a given repository.
     *
     * @param repo
     *            the repository the walker will obtain data from. An
     *            ObjectReader will be created by the walker, and will be closed
     *            when the walker is closed.
     */
    public TreeWalk(Repository repo) {
        this(repo, repo.newObjectReader(), true);
    }

    /**
     * Create a new tree walker for a given repository.
     *
     * @param repo
     *            the repository the walker will obtain data from. An
     *            ObjectReader will be created by the walker, and will be closed
     *            when the walker is closed.
     * @param or
     *            the reader the walker will obtain tree data from. The reader
     *            is not closed when the walker is closed.
     * @since 4.3
     */
    public TreeWalk(@Nullable Repository repo, ObjectReader or) {
        this(repo, or, false);
    }

    /**
     * Create a new tree walker for a given repository.
     *
     * @param or
     *            the reader the walker will obtain tree data from. The reader
     *            is not closed when the walker is closed.
     */
    public TreeWalk(ObjectReader or) {
        this(null, or, false);
    }

    private TreeWalk(final @Nullable Repository repo, final ObjectReader or,
            final boolean closeReader) {
        if (repo != null) {
            config = repo.getConfig();
            attributesNodeProvider = repo.createAttributesNodeProvider();
            filterCommands = FilterCommandRegistry
                    .getRegisteredFilterCommands();
        } else {
            config = null;
            attributesNodeProvider = null;
        }
        reader = or;
        filter = TreeFilter.ALL;
        trees = NO_TREES;
        this.closeReader = closeReader;
    }

    /**
     * Get the reader this walker is using to load objects.
     *
     * @return the reader this walker is using to load objects.
     */
    public ObjectReader getObjectReader() {
        return reader;
    }

    /**
     * Get the operation type
     *
     * @return the {@link org.eclipse.jgit.treewalk.TreeWalk.OperationType}
     * @since 4.3
     */
    public OperationType getOperationType() {
        return operationType;
    }

    /**
     * {@inheritDoc}
     * <p>
     * Release any resources used by this walker's reader.
     * <p>
     * A walker that has been released can be used again, but may need to be
     * released after the subsequent usage.
     *
     * @since 4.0
     */
    @Override
    public void close() {
        if (closeReader) {
            reader.close();
        }
    }

    /**
     * Get the currently configured filter.
     *
     * @return the current filter. Never null as a filter is always needed.
     */
    public TreeFilter getFilter() {
        return filter;
    }

    /**
     * Set the tree entry filter for this walker.
     * <p>
     * Multiple filters may be combined by constructing an arbitrary tree of
     * <code>AndTreeFilter</code> or <code>OrTreeFilter</code> instances to
     * describe the boolean expression required by the application. Custom
     * filter implementations may also be constructed by applications.
     * <p>
     * Note that filters are not thread-safe and may not be shared by concurrent
     * TreeWalk instances. Every TreeWalk must be supplied its own unique
     * filter, unless the filter implementation specifically states it is (and
     * always will be) thread-safe. Callers may use
     * {@link org.eclipse.jgit.treewalk.filter.TreeFilter#clone()} to create a
     * unique filter tree for this TreeWalk instance.
     *
     * @param newFilter
     *            the new filter. If null the special
     *            {@link org.eclipse.jgit.treewalk.filter.TreeFilter#ALL} filter
     *            will be used instead, as it matches every entry.
     * @see org.eclipse.jgit.treewalk.filter.AndTreeFilter
     * @see org.eclipse.jgit.treewalk.filter.OrTreeFilter
     */
    public void setFilter(TreeFilter newFilter) {
        filter = newFilter != null ? newFilter : TreeFilter.ALL;
    }

    /**
     * Is this walker automatically entering into subtrees?
     * <p>
     * If the walker is recursive then the caller will not see a subtree node
     * and instead will only receive file nodes in all relevant subtrees.
     *
     * @return true if automatically entering subtrees is enabled.
     */
    public boolean isRecursive() {
        return recursive;
    }

    /**
     * Set the walker to enter (or not enter) subtrees automatically.
     * <p>
     * If recursive mode is enabled the walker will hide subtree nodes from the
     * calling application and will produce only file level nodes. If a tree
     * (directory) is deleted then all of the file level nodes will appear to be
     * deleted, recursively, through as many levels as necessary to account for
     * all entries.
     *
     * @param b
     *            true to skip subtree nodes and only obtain files nodes.
     */
    public void setRecursive(boolean b) {
        recursive = b;
    }

    /**
     * Does this walker return a tree entry after it exits the subtree?
     * <p>
     * If post order traversal is enabled then the walker will return a subtree
     * after it has returned the last entry within that subtree. This may cause
     * a subtree to be seen by the application twice if {@link #isRecursive()}
     * is false, as the application will see it once, call
     * {@link #enterSubtree()}, and then see it again as it leaves the subtree.
     * <p>
     * If an application does not enable {@link #isRecursive()} and it does not
     * call {@link #enterSubtree()} then the tree is returned only once as none
     * of the children were processed.
     *
     * @return true if subtrees are returned after entries within the subtree.
     */
    public boolean isPostOrderTraversal() {
        return postOrderTraversal;
    }

    /**
     * Set the walker to return trees after their children.
     *
     * @param b
     *            true to get trees after their children.
     * @see #isPostOrderTraversal()
     */
    public void setPostOrderTraversal(boolean b) {
        postOrderTraversal = b;
    }

    /**
     * Sets the {@link org.eclipse.jgit.attributes.AttributesNodeProvider} for
     * this {@link org.eclipse.jgit.treewalk.TreeWalk}.
     * <p>
     * This is a requirement for a correct computation of the git attributes. If
     * this {@link org.eclipse.jgit.treewalk.TreeWalk} has been built using
     * {@link #TreeWalk(Repository)} constructor, the
     * {@link org.eclipse.jgit.attributes.AttributesNodeProvider} has already
     * been set. Indeed,the {@link org.eclipse.jgit.lib.Repository} can provide
     * an {@link org.eclipse.jgit.attributes.AttributesNodeProvider} using
     * {@link org.eclipse.jgit.lib.Repository#createAttributesNodeProvider()}
     * method. Otherwise you should provide one.
     * </p>
     *
     * @see Repository#createAttributesNodeProvider()
     * @param provider
     *            a {@link org.eclipse.jgit.attributes.AttributesNodeProvider}
     *            object.
     * @since 4.2
     */
    public void setAttributesNodeProvider(AttributesNodeProvider provider) {
        attributesNodeProvider = provider;
    }

    /**
     * Get the attributes node provider
     *
     * @return the {@link org.eclipse.jgit.attributes.AttributesNodeProvider}
     *         for this {@link org.eclipse.jgit.treewalk.TreeWalk}.
     * @since 4.3
     */
    public AttributesNodeProvider getAttributesNodeProvider() {
        return attributesNodeProvider;
    }

    /**
     * Identifies the tree at the given index as the head tree. This is the tree
     * use by default to determine attributes and EOL modes.
     *
     * @param index
     *            of the tree to use as head
     * @throws IllegalArgumentException
     *             if the index is out of range
     * @since 6.1
     */
    public void setHead(int index) {
        if (index < 0 || index >= trees.length) {
            throw new IllegalArgumentException("Head index " + index //$NON-NLS-1$
                    + " out of range [0," + trees.length + ')'); //$NON-NLS-1$
        }
        headIndex = index;
    }

    /**
     * {@inheritDoc}
     * <p>
     * Retrieve the git attributes for the current entry.
     *
     * <h3>Git attribute computation</h3>
     *
     * <ul>
     * <li>Get the attributes matching the current path entry from the info file
     * (see {@link AttributesNodeProvider#getInfoAttributesNode()}).</li>
     * <li>Completes the list of attributes using the .gitattributes files
     * located on the current path (the further the directory that contains
     * .gitattributes is from the path in question, the lower its precedence).
     * For a checkin operation, it will look first on the working tree (if any).
     * If there is no attributes file, it will fallback on the index. For a
     * checkout operation, it will first use the index entry and then fallback
     * on the working tree if none.</li>
     * <li>In the end, completes the list of matching attributes using the
     * global attribute file define in the configuration (see
     * {@link AttributesNodeProvider#getGlobalAttributesNode()})</li>
     *
     * </ul>
     *
     *
     * <h3>Iterator constraints</h3>
     *
     * <p>
     * In order to have a correct list of attributes for the current entry, this
     * {@link TreeWalk} requires to have at least one
     * {@link AttributesNodeProvider} and a {@link DirCacheIterator} set up. An
     * {@link AttributesNodeProvider} is used to retrieve the attributes from
     * the info attributes file and the global attributes file. The
     * {@link DirCacheIterator} is used to retrieve the .gitattributes files
     * stored in the index. A {@link WorkingTreeIterator} can also be provided
     * to access the local version of the .gitattributes files. If none is
     * provided it will fallback on the {@link DirCacheIterator}.
     * </p>
     *
     * @since 4.2
     */
    @Override
    public Attributes getAttributes() {
        return getAttributes(headIndex);
    }

    /**
     * Retrieves the git attributes based on the given tree.
     *
     * @param index
     *            of the tree to use as base for the attributes
     * @return the attributes
     * @since 6.1
     */
    public Attributes getAttributes(int index) {
        int attrIndex = index + 1;
        Attributes result = attrs[attrIndex];
        if (result != null) {
            return result;
        }
        if (attributesNodeProvider == null) {
            throw new IllegalStateException(
                    "The tree walk should have one AttributesNodeProvider set in order to compute the git attributes."); //$NON-NLS-1$
        }

        try {
            AttributesHandler handler = attributesHandlers[attrIndex];
            if (handler == null) {
                if (index < 0) {
                    // Legacy behavior (headIndex not set, getAttributes() above
                    // called)
                    handler = new AttributesHandler(this, () -> {
                        return getTree(CanonicalTreeParser.class);
                    });
                } else {
                    handler = new AttributesHandler(this, () -> {
                        AbstractTreeIterator tree = trees[index];
                        if (tree instanceof CanonicalTreeParser) {
                            return (CanonicalTreeParser) tree;
                        }
                        return null;
                    });
                }
                attributesHandlers[attrIndex] = handler;
            }
            result = handler.getAttributes();
            attrs[attrIndex] = result;
            return result;
        } catch (IOException e) {
            throw new JGitInternalException("Error while parsing attributes", //$NON-NLS-1$
                    e);
        }
    }

    /**
     * Get the EOL stream type of the current entry using the config and
     * {@link #getAttributes()}.
     *
     * @param opType
     *            the operationtype (checkin/checkout) which should be used
     * @return the EOL stream type of the current entry using the config and
     *         {@link #getAttributes()}. Note that this method may return null
     *         if the {@link org.eclipse.jgit.treewalk.TreeWalk} is not based on
     *         a working tree
     * @since 4.10
     */
    @Nullable
    public EolStreamType getEolStreamType(OperationType opType) {
        if (attributesNodeProvider == null || config == null) {
            return null;
        }
        OperationType op = opType != null ? opType : operationType;
        return EolStreamTypeUtil.detectStreamType(op,
                config.get(WorkingTreeOptions.KEY), getAttributes());
    }

    /**
     * Get the EOL stream type of the current entry for checking out using the
     * config and {@link #getAttributes()}.
     *
     * @param tree
     *            index of the tree the check-out is to be from
     * @return the EOL stream type of the current entry using the config and
     *         {@link #getAttributes()}. Note that this method may return null
     *         if the {@link org.eclipse.jgit.treewalk.TreeWalk} is not based on
     *         a working tree
     * @since 6.1
     */
    @Nullable
    public EolStreamType getCheckoutEolStreamType(int tree) {
        if (attributesNodeProvider == null || config == null) {
            return null;
        }
        Attributes attr = getAttributes(tree);
        return EolStreamTypeUtil.detectStreamType(OperationType.CHECKOUT_OP,
                config.get(WorkingTreeOptions.KEY), attr);
    }

    /**
     * Reset this walker so new tree iterators can be added to it.
     */
    public void reset() {
        attrs = null;
        attributesHandlers = null;
        headIndex = -1;
        trees = NO_TREES;
        advance = false;
        depth = 0;
    }

    /**
     * Reset this walker to run over a single existing tree.
     *
     * @param id
     *            the tree we need to parse. The walker will execute over this
     *            single tree if the reset is successful.
     * @throws org.eclipse.jgit.errors.MissingObjectException
     *             the given tree object does not exist in this repository.
     * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
     *             the given object id does not denote a tree, but instead names
     *             some other non-tree type of object. Note that commits are not
     *             trees, even if they are sometimes called a "tree-ish".
     * @throws org.eclipse.jgit.errors.CorruptObjectException
     *             the object claimed to be a tree, but its contents did not
     *             appear to be a tree. The repository may have data corruption.
     * @throws java.io.IOException
     *             a loose object or pack file could not be read.
     */
    public void reset(AnyObjectId id) throws MissingObjectException,
            IncorrectObjectTypeException, CorruptObjectException, IOException {
        if (trees.length == 1) {
            AbstractTreeIterator o = trees[0];
            while (o.parent != null)
                o = o.parent;
            if (o instanceof CanonicalTreeParser) {
                o.matches = null;
                o.matchShift = 0;
                ((CanonicalTreeParser) o).reset(reader, id);
                trees[0] = o;
            } else {
                trees[0] = parserFor(id);
            }
        } else {
            trees = new AbstractTreeIterator[] { parserFor(id) };
        }

        advance = false;
        depth = 0;
        attrs = new Attributes[2];
        attributesHandlers = new AttributesHandler[2];
        headIndex = -1;
    }

    /**
     * Reset this walker to run over a set of existing trees.
     *
     * @param ids
     *            the trees we need to parse. The walker will execute over this
     *            many parallel trees if the reset is successful.
     * @throws org.eclipse.jgit.errors.MissingObjectException
     *             the given tree object does not exist in this repository.
     * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
     *             the given object id does not denote a tree, but instead names
     *             some other non-tree type of object. Note that commits are not
     *             trees, even if they are sometimes called a "tree-ish".
     * @throws org.eclipse.jgit.errors.CorruptObjectException
     *             the object claimed to be a tree, but its contents did not
     *             appear to be a tree. The repository may have data corruption.
     * @throws java.io.IOException
     *             a loose object or pack file could not be read.
     */
    public void reset(AnyObjectId... ids) throws MissingObjectException,
            IncorrectObjectTypeException, CorruptObjectException, IOException {
        final int oldLen = trees.length;
        final int newLen = ids.length;
        final AbstractTreeIterator[] r = newLen == oldLen ? trees
                : new AbstractTreeIterator[newLen];
        for (int i = 0; i < newLen; i++) {
            AbstractTreeIterator o;

            if (i < oldLen) {
                o = trees[i];
                while (o.parent != null)
                    o = o.parent;
                if (o instanceof CanonicalTreeParser && o.pathOffset == 0) {
                    o.matches = null;
                    o.matchShift = 0;
                    ((CanonicalTreeParser) o).reset(reader, ids[i]);
                    r[i] = o;
                    continue;
                }
            }

            o = parserFor(ids[i]);
            r[i] = o;
        }

        trees = r;
        advance = false;
        depth = 0;
        if (oldLen == newLen) {
            Arrays.fill(attrs, null);
            Arrays.fill(attributesHandlers, null);
        } else {
            attrs = new Attributes[newLen + 1];
            attributesHandlers = new AttributesHandler[newLen + 1];
        }
        headIndex = -1;
    }

    /**
     * Add an already existing tree object for walking.
     * <p>
     * The position of this tree is returned to the caller, in case the caller
     * has lost track of the order they added the trees into the walker.
     * <p>
     * The tree must have the same root as existing trees in the walk.
     *
     * @param id
     *            identity of the tree object the caller wants walked.
     * @return position of this tree within the walker.
     * @throws org.eclipse.jgit.errors.MissingObjectException
     *             the given tree object does not exist in this repository.
     * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
     *             the given object id does not denote a tree, but instead names
     *             some other non-tree type of object. Note that commits are not
     *             trees, even if they are sometimes called a "tree-ish".
     * @throws org.eclipse.jgit.errors.CorruptObjectException
     *             the object claimed to be a tree, but its contents did not
     *             appear to be a tree. The repository may have data corruption.
     * @throws java.io.IOException
     *             a loose object or pack file could not be read.
     */
    public int addTree(AnyObjectId id) throws MissingObjectException,
            IncorrectObjectTypeException, CorruptObjectException, IOException {
        return addTree(parserFor(id));
    }

    /**
     * Add an already created tree iterator for walking.
     * <p>
     * The position of this tree is returned to the caller, in case the caller
     * has lost track of the order they added the trees into the walker.
     * <p>
     * The tree which the iterator operates on must have the same root as
     * existing trees in the walk.
     *
     * @param p
     *            an iterator to walk over. The iterator should be new, with no
     *            parent, and should still be positioned before the first entry.
     *            The tree which the iterator operates on must have the same
     *            root as other trees in the walk.
     * @return position of this tree within the walker.
     */
    public int addTree(AbstractTreeIterator p) {
        int n = trees.length;
        AbstractTreeIterator[] newTrees = new AbstractTreeIterator[n + 1];

        System.arraycopy(trees, 0, newTrees, 0, n);
        newTrees[n] = p;
        p.matches = null;
        p.matchShift = 0;

        trees = newTrees;
        if (attrs == null) {
            attrs = new Attributes[n + 2];
        } else {
            attrs = Arrays.copyOf(attrs, n + 2);
        }
        if (attributesHandlers == null) {
            attributesHandlers = new AttributesHandler[n + 2];
        } else {
            attributesHandlers = Arrays.copyOf(attributesHandlers, n + 2);
        }
        return n;
    }

    /**
     * Get the number of trees known to this walker.
     *
     * @return the total number of trees this walker is iterating over.
     */
    public int getTreeCount() {
        return trees.length;
    }

    /**
     * Advance this walker to the next relevant entry.
     *
     * @return true if there is an entry available; false if all entries have
     *         been walked and the walk of this set of tree iterators is over.
     * @throws org.eclipse.jgit.errors.MissingObjectException
     *             {@link #isRecursive()} was enabled, a subtree was found, but
     *             the subtree object does not exist in this repository. The
     *             repository may be missing objects.
     * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
     *             {@link #isRecursive()} was enabled, a subtree was found, and
     *             the subtree id does not denote a tree, but instead names some
     *             other non-tree type of object. The repository may have data
     *             corruption.
     * @throws org.eclipse.jgit.errors.CorruptObjectException
     *             the contents of a tree did not appear to be a tree. The
     *             repository may have data corruption.
     * @throws java.io.IOException
     *             a loose object or pack file could not be read.
     */
    public boolean next() throws MissingObjectException,
            IncorrectObjectTypeException, CorruptObjectException, IOException {
        try {
            if (advance) {
                advance = false;
                postChildren = false;
                popEntriesEqual();
            }

            for (;;) {
                Arrays.fill(attrs, null);
                final AbstractTreeIterator t = min();
                if (t.eof()) {
                    if (depth > 0) {
                        exitSubtree();
                        if (postOrderTraversal) {
                            advance = true;
                            postChildren = true;
                            return true;
                        }
                        popEntriesEqual();
                        continue;
                    }
                    return false;
                }

                currentHead = t;
                if (filter.matchFilter(this) == 1) {
                    skipEntriesEqual();
                    continue;
                }

                if (recursive && FileMode.TREE.equals(t.mode)) {
                    enterSubtree();
                    continue;
                }

                advance = true;
                return true;
            }
        } catch (StopWalkException stop) {
            stopWalk();
            return false;
        }
    }

    /**
     * Notify iterators the walk is aborting.
     * <p>
     * Primarily to notify {@link DirCacheBuildIterator} the walk is aborting so
     * that it can copy any remaining entries.
     *
     * @throws IOException
     *             if traversal of remaining entries throws an exception during
     *             object access. This should never occur as remaining trees
     *             should already be in memory, however the methods used to
     *             finish traversal are declared to throw IOException.
     */
    void stopWalk() throws IOException {
        for (AbstractTreeIterator t : trees) {
            t.stopWalk();
        }
    }

    /**
     * Obtain the tree iterator for the current entry.
     * <p>
     * Entering into (or exiting out of) a subtree causes the current tree
     * iterator instance to be changed for the nth tree. This allows the tree
     * iterators to manage only one list of items, with the diving handled by
     * recursive trees.
     *
     * @param nth
     *            tree to obtain the current iterator of.
     * @param clazz
     *            type of the tree iterator expected by the caller.
     * @return r the current iterator of the requested type; null if the tree
     *         has no entry to match the current path.
     */
    @SuppressWarnings("unchecked")
    public <T extends AbstractTreeIterator> T getTree(final int nth,
            final Class<T> clazz) {
        final AbstractTreeIterator t = trees[nth];
        return t.matches == currentHead ? (T) t : null;
    }

    /**
     * Obtain the raw {@link org.eclipse.jgit.lib.FileMode} bits for the current
     * entry.
     * <p>
     * Every added tree supplies mode bits, even if the tree does not contain
     * the current entry. In the latter case
     * {@link org.eclipse.jgit.lib.FileMode#MISSING}'s mode bits (0) are
     * returned.
     *
     * @param nth
     *            tree to obtain the mode bits from.
     * @return mode bits for the current entry of the nth tree.
     * @see FileMode#fromBits(int)
     */
    public int getRawMode(int nth) {
        final AbstractTreeIterator t = trees[nth];
        return t.matches == currentHead ? t.mode : 0;
    }

    /**
     * Obtain the {@link org.eclipse.jgit.lib.FileMode} for the current entry.
     * <p>
     * Every added tree supplies a mode, even if the tree does not contain the
     * current entry. In the latter case
     * {@link org.eclipse.jgit.lib.FileMode#MISSING} is returned.
     *
     * @param nth
     *            tree to obtain the mode from.
     * @return mode for the current entry of the nth tree.
     */
    public FileMode getFileMode(int nth) {
        return FileMode.fromBits(getRawMode(nth));
    }

    /**
     * Obtain the {@link org.eclipse.jgit.lib.FileMode} for the current entry on
     * the currentHead tree
     *
     * @return mode for the current entry of the currentHead tree.
     * @since 4.3
     */
    public FileMode getFileMode() {
        return FileMode.fromBits(currentHead.mode);
    }

    /**
     * Obtain the ObjectId for the current entry.
     * <p>
     * Using this method to compare ObjectId values between trees of this walker
     * is very inefficient. Applications should try to use
     * {@link #idEqual(int, int)} or {@link #getObjectId(MutableObjectId, int)}
     * whenever possible.
     * <p>
     * Every tree supplies an object id, even if the tree does not contain the
     * current entry. In the latter case
     * {@link org.eclipse.jgit.lib.ObjectId#zeroId()} is returned.
     *
     * @param nth
     *            tree to obtain the object identifier from.
     * @return object identifier for the current tree entry.
     * @see #getObjectId(MutableObjectId, int)
     * @see #idEqual(int, int)
     * @see #getObjectId(MutableObjectId, int)
     * @see #idEqual(int, int)
     */
    public ObjectId getObjectId(int nth) {
        final AbstractTreeIterator t = trees[nth];
        return t.matches == currentHead ? t.getEntryObjectId() : ObjectId
                .zeroId();
    }

    /**
     * Obtain the ObjectId for the current entry.
     * <p>
     * Every tree supplies an object id, even if the tree does not contain the
     * current entry. In the latter case
     * {@link org.eclipse.jgit.lib.ObjectId#zeroId()} is supplied.
     * <p>
     * Applications should try to use {@link #idEqual(int, int)} when possible
     * as it avoids conversion overheads.
     *
     * @param out
     *            buffer to copy the object id into.
     * @param nth
     *            tree to obtain the object identifier from.
     * @see #idEqual(int, int)
     */
    public void getObjectId(MutableObjectId out, int nth) {
        final AbstractTreeIterator t = trees[nth];
        if (t.matches == currentHead)
            t.getEntryObjectId(out);
        else
            out.clear();
    }

    /**
     * Compare two tree's current ObjectId values for equality.
     *
     * @param nthA
     *            first tree to compare the object id from.
     * @param nthB
     *            second tree to compare the object id from.
     * @return result of
     *         <code>getObjectId(nthA).equals(getObjectId(nthB))</code>.
     * @see #getObjectId(int)
     */
    public boolean idEqual(int nthA, int nthB) {
        final AbstractTreeIterator ch = currentHead;
        final AbstractTreeIterator a = trees[nthA];
        final AbstractTreeIterator b = trees[nthB];
        if (a.matches != ch && b.matches != ch) {
            // If neither tree matches the current path node then neither
            // tree has this entry. In such case the ObjectId is zero(),
            // and zero() is always equal to zero().
            //
            return true;
        }
        if (!a.hasId() || !b.hasId())
            return false;
        if (a.matches == ch && b.matches == ch)
            return a.idEqual(b);
        return false;
    }

    /**
     * Get the current entry's name within its parent tree.
     * <p>
     * This method is not very efficient and is primarily meant for debugging
     * and final output generation. Applications should try to avoid calling it,
     * and if invoked do so only once per interesting entry, where the name is
     * absolutely required for correct function.
     *
     * @return name of the current entry within the parent tree (or directory).
     *         The name never includes a '/'.
     */
    public String getNameString() {
        final AbstractTreeIterator t = currentHead;
        final int off = t.pathOffset;
        final int end = t.pathLen;
        return RawParseUtils.decode(UTF_8, t.path, off, end);
    }

    /**
     * Get the current entry's complete path.
     * <p>
     * This method is not very efficient and is primarily meant for debugging
     * and final output generation. Applications should try to avoid calling it,
     * and if invoked do so only once per interesting entry, where the name is
     * absolutely required for correct function.
     *
     * @return complete path of the current entry, from the root of the
     *         repository. If the current entry is in a subtree there will be at
     *         least one '/' in the returned string.
     */
    public String getPathString() {
        return pathOf(currentHead);
    }

    /**
     * Get the current entry's complete path as a UTF-8 byte array.
     *
     * @return complete path of the current entry, from the root of the
     *         repository. If the current entry is in a subtree there will be at
     *         least one '/' in the returned string.
     */
    public byte[] getRawPath() {
        final AbstractTreeIterator t = currentHead;
        final int n = t.pathLen;
        final byte[] r = new byte[n];
        System.arraycopy(t.path, 0, r, 0, n);
        return r;
    }

    /**
     * Get the path length of the current entry.
     *
     * @return The path length of the current entry.
     */
    public int getPathLength() {
        return currentHead.pathLen;
    }

    /**
     * Test if the supplied path matches the current entry's path.
     * <p>
     * This method detects if the supplied path is equal to, a subtree of, or
     * not similar at all to the current entry. It is faster to use this
     * method than to use {@link #getPathString()} to first create a String
     * object, then test <code>startsWith</code> or some other type of string
     * match function.
     * <p>
     * If the current entry is a subtree, then all paths within the subtree
     * are considered to match it.
     *
     * @param p
     *            path buffer to test. Callers should ensure the path does not
     *            end with '/' prior to invocation.
     * @param pLen
     *            number of bytes from <code>buf</code> to test.
     * @return -1 if the current path is a parent to p; 0 if p matches the current
     *         path; 1 if the current path is different and will never match
     *         again on this tree walk.
     * @since 4.7
     */
    public int isPathMatch(byte[] p, int pLen) {
        final AbstractTreeIterator t = currentHead;
        final byte[] c = t.path;
        final int cLen = t.pathLen;
        int ci;

        for (ci = 0; ci < cLen && ci < pLen; ci++) {
            final int c_value = (c[ci] & 0xff) - (p[ci] & 0xff);
            if (c_value != 0) {
                // Paths do not and will never match
                return 1;
            }
        }

        if (ci < cLen) {
            // Ran out of pattern but we still had current data.
            // If c[ci] == '/' then pattern matches the subtree.
            // Otherwise it is a partial match == miss
            return c[ci] == '/' ? 0 : 1;
        }

        if (ci < pLen) {
            // Ran out of current, but we still have pattern data.
            // If p[ci] == '/' then this subtree is a parent in the pattern,
            // otherwise it's a miss.
            return p[ci] == '/' && FileMode.TREE.equals(t.mode) ? -1 : 1;
        }

        // Both strings are identical.
        return 0;
    }

    /**
     * Test if the supplied path matches the current entry's path.
     * <p>
     * This method tests that the supplied path is exactly equal to the current
     * entry or is one of its parent directories. It is faster to use this
     * method then to use {@link #getPathString()} to first create a String
     * object, then test <code>startsWith</code> or some other type of string
     * match function.
     * <p>
     * If the current entry is a subtree, then all paths within the subtree
     * are considered to match it.
     *
     * @param p
     *            path buffer to test. Callers should ensure the path does not
     *            end with '/' prior to invocation.
     * @param pLen
     *            number of bytes from <code>buf</code> to test.
     * @return &lt; 0 if p is before the current path; 0 if p matches the current
     *         path; 1 if the current path is past p and p will never match
     *         again on this tree walk.
     */
    public int isPathPrefix(byte[] p, int pLen) {
        final AbstractTreeIterator t = currentHead;
        final byte[] c = t.path;
        final int cLen = t.pathLen;
        int ci;

        for (ci = 0; ci < cLen && ci < pLen; ci++) {
            final int c_value = (c[ci] & 0xff) - (p[ci] & 0xff);
            if (c_value != 0)
                return c_value;
        }

        if (ci < cLen) {
            // Ran out of pattern but we still had current data.
            // If c[ci] == '/' then pattern matches the subtree.
            // Otherwise we cannot be certain so we return -1.
            //
            return c[ci] == '/' ? 0 : -1;
        }

        if (ci < pLen) {
            // Ran out of current, but we still have pattern data.
            // If p[ci] == '/' then pattern matches this subtree,
            // otherwise we cannot be certain so we return -1.
            //
            return p[ci] == '/' && FileMode.TREE.equals(t.mode) ? 0 : -1;
        }

        // Both strings are identical.
        //
        return 0;
    }

    /**
     * Test if the supplied path matches (being suffix of) the current entry's
     * path.
     * <p>
     * This method tests that the supplied path is exactly equal to the current
     * entry, or is relative to one of entry's parent directories. It is faster
     * to use this method then to use {@link #getPathString()} to first create
     * a String object, then test <code>endsWith</code> or some other type of
     * string match function.
     *
     * @param p
     *            path buffer to test.
     * @param pLen
     *            number of bytes from <code>buf</code> to test.
     * @return true if p is suffix of the current path;
     *         false if otherwise
     */
    public boolean isPathSuffix(byte[] p, int pLen) {
        final AbstractTreeIterator t = currentHead;
        final byte[] c = t.path;
        final int cLen = t.pathLen;

        for (int i = 1; i <= pLen; i++) {
            // Pattern longer than current path
            if (i > cLen)
                return false;
            // Current path doesn't match pattern
            if (c[cLen - i] != p[pLen - i])
                return false;
        }

        // Whole pattern tested -> matches
        return true;
    }

    /**
     * Get the current subtree depth of this walker.
     *
     * @return the current subtree depth of this walker.
     */
    public int getDepth() {
        return depth;
    }

    /**
     * Is the current entry a subtree?
     * <p>
     * This method is faster then testing the raw mode bits of all trees to see
     * if any of them are a subtree. If at least one is a subtree then this
     * method will return true.
     *
     * @return true if {@link #enterSubtree()} will work on the current node.
     */
    public boolean isSubtree() {
        return FileMode.TREE.equals(currentHead.mode);
    }

    /**
     * Is the current entry a subtree returned after its children?
     *
     * @return true if the current node is a tree that has been returned after
     *         its children were already processed.
     * @see #isPostOrderTraversal()
     */
    public boolean isPostChildren() {
        return postChildren && isSubtree();
    }

    /**
     * Enter into the current subtree.
     * <p>
     * If the current entry is a subtree this method arranges for its children
     * to be returned before the next sibling following the subtree is returned.
     *
     * @throws org.eclipse.jgit.errors.MissingObjectException
     *             a subtree was found, but the subtree object does not exist in
     *             this repository. The repository may be missing objects.
     * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
     *             a subtree was found, and the subtree id does not denote a
     *             tree, but instead names some other non-tree type of object.
     *             The repository may have data corruption.
     * @throws org.eclipse.jgit.errors.CorruptObjectException
     *             the contents of a tree did not appear to be a tree. The
     *             repository may have data corruption.
     * @throws java.io.IOException
     *             a loose object or pack file could not be read.
     */
    public void enterSubtree() throws MissingObjectException,
            IncorrectObjectTypeException, CorruptObjectException, IOException {
        Arrays.fill(attrs, null);
        final AbstractTreeIterator ch = currentHead;
        final AbstractTreeIterator[] tmp = new AbstractTreeIterator[trees.length];
        for (int i = 0; i < trees.length; i++) {
            final AbstractTreeIterator t = trees[i];
            final AbstractTreeIterator n;
            // If we find a GITLINK when attempting to enter a subtree, then the
            // GITLINK must exist as a TREE in the index, meaning the working tree
            // entry should be treated as a TREE
            if (t.matches == ch && !t.eof() &&
                    (FileMode.TREE.equals(t.mode)
                            || (FileMode.GITLINK.equals(t.mode) && t.isWorkTree())))
                n = t.createSubtreeIterator(reader, idBuffer);
            else
                n = t.createEmptyTreeIterator();
            tmp[i] = n;
        }
        depth++;
        advance = false;
        System.arraycopy(tmp, 0, trees, 0, trees.length);
    }

    /**
     * Returns an AbstractTreeIterator from {@code trees} with the smallest name, and sets its
     * {@code matches} field. This may clobber {@code matches} in other {@code tree}s. Other iterators
     * at the same name will have their {@code matches} pointing to the same {@code min()} value.
     *
     * @return the smallest tree iterator available.
     * @throws CorruptObjectException
     */
    @SuppressWarnings("unused")
    AbstractTreeIterator min() throws CorruptObjectException {
        int i = 0;
        AbstractTreeIterator minRef = trees[i];
        while (minRef.eof() && ++i < trees.length)
            minRef = trees[i];
        if (minRef.eof())
            return minRef;

        minRef.matches = minRef;
        while (++i < trees.length) {
            final AbstractTreeIterator t = trees[i];
            if (t.eof())
                continue;
            final int cmp = t.pathCompare(minRef);
            if (cmp < 0) {
                t.matches = t;
                minRef = t;
            } else if (cmp == 0) {
                t.matches = minRef;
            }
        }

        return minRef;
    }

    void popEntriesEqual() throws CorruptObjectException {
        final AbstractTreeIterator ch = currentHead;
        for (AbstractTreeIterator t : trees) {
            if (t.matches == ch) {
                t.next(1);
                t.matches = null;
            }
        }
    }

    void skipEntriesEqual() throws CorruptObjectException {
        final AbstractTreeIterator ch = currentHead;
        for (AbstractTreeIterator t : trees) {
            if (t.matches == ch) {
                t.skip();
                t.matches = null;
            }
        }
    }

    void exitSubtree() {
        depth--;
        for (int i = 0; i < trees.length; i++)
            trees[i] = trees[i].parent;

        AbstractTreeIterator minRef = null;
        for (AbstractTreeIterator t : trees) {
            if (t.matches != t)
                continue;
            if (minRef == null || t.pathCompare(minRef) < 0)
                minRef = t;
        }
        currentHead = minRef;
    }

    private CanonicalTreeParser parserFor(AnyObjectId id)
            throws IncorrectObjectTypeException, IOException {
        final CanonicalTreeParser p = new CanonicalTreeParser();
        p.reset(reader, id);
        return p;
    }

    static String pathOf(AbstractTreeIterator t) {
        return RawParseUtils.decode(UTF_8, t.path, 0, t.pathLen);
    }

    static String pathOf(byte[] buf, int pos, int end) {
        return RawParseUtils.decode(UTF_8, buf, pos, end);
    }

    /**
     * Get the tree of that type.
     *
     * @param type
     *            of the tree to be queried
     * @return the tree of that type or null if none is present.
     * @since 4.3
     * @param <T>
     *            a tree type.
     */
    public <T extends AbstractTreeIterator> T getTree(Class<T> type) {
        for (AbstractTreeIterator tree : trees) {
            if (type.isInstance(tree)) {
                return type.cast(tree);
            }
        }
        return null;
    }

    /**
     * Inspect config and attributes to return a filtercommand applicable for
     * the current path.
     *
     * @param filterCommandType
     *            which type of filterCommand should be executed. E.g. "clean",
     *            "smudge". For "smudge" consider using
     *            {{@link #getSmudgeCommand(int)} instead.
     * @return a filter command
     * @throws java.io.IOException
     * @since 4.2
     */
    public String getFilterCommand(String filterCommandType)
            throws IOException {
        Attributes attributes = getAttributes();

        Attribute f = attributes.get(Constants.ATTR_FILTER);
        if (f == null) {
            return null;
        }
        String filterValue = f.getValue();
        if (filterValue == null) {
            return null;
        }

        String filterCommand = getFilterCommandDefinition(filterValue,
                filterCommandType);
        if (filterCommand == null) {
            return null;
        }
        return filterCommand.replaceAll("%f", //$NON-NLS-1$
                Matcher.quoteReplacement(
                        QuotedString.BOURNE.quote((getPathString()))));
    }

    /**
     * Inspect config and attributes to return a filtercommand applicable for
     * the current path.
     *
     * @param index
     *            of the tree the item to be smudged is in
     * @return a filter command
     * @throws java.io.IOException
     * @since 6.1
     */
    public String getSmudgeCommand(int index)
            throws IOException {
        return getSmudgeCommand(getAttributes(index));
    }

    /**
     * Inspect config and attributes to return a filtercommand applicable for
     * the current path.
     *
     * @param attributes
     *            to use
     * @return a filter command
     * @throws java.io.IOException
     * @since 6.1
     */
    public String getSmudgeCommand(Attributes attributes) throws IOException {
        if (attributes == null) {
            return null;
        }
        Attribute f = attributes.get(Constants.ATTR_FILTER);
        if (f == null) {
            return null;
        }
        String filterValue = f.getValue();
        if (filterValue == null) {
            return null;
        }

        String filterCommand = getFilterCommandDefinition(filterValue,
                Constants.ATTR_FILTER_TYPE_SMUDGE);
        if (filterCommand == null) {
            return null;
        }
        return filterCommand.replaceAll("%f", //$NON-NLS-1$
                Matcher.quoteReplacement(
                        QuotedString.BOURNE.quote((getPathString()))));
    }

    /**
     * Get the filter command how it is defined in gitconfig. The returned
     * string may contain "%f" which needs to be replaced by the current path
     * before executing the filter command. These filter definitions are cached
     * for better performance.
     *
     * @param filterDriverName
     *            The name of the filter driver as it is referenced in the
     *            gitattributes file. E.g. "lfs". For each filter driver there
     *            may be many commands defined in the .gitconfig
     * @param filterCommandType
     *            The type of the filter command for a specific filter driver.
     *            May be "clean" or "smudge".
     * @return the definition of the command to be executed for this filter
     *         driver and filter command
     */
    private String getFilterCommandDefinition(String filterDriverName,
            String filterCommandType) {
        String key = filterDriverName + "." + filterCommandType; //$NON-NLS-1$
        String filterCommand = filterCommandsByNameDotType.get(key);
        if (filterCommand != null)
            return filterCommand;
        filterCommand = config.getString(ConfigConstants.CONFIG_FILTER_SECTION,
                filterDriverName, filterCommandType);
        boolean useBuiltin = config.getBoolean(
                ConfigConstants.CONFIG_FILTER_SECTION,
                filterDriverName, ConfigConstants.CONFIG_KEY_USEJGITBUILTIN, false);
        if (useBuiltin) {
            String builtinFilterCommand = Constants.BUILTIN_FILTER_PREFIX
                    + filterDriverName + '/' + filterCommandType;
            if (filterCommands != null
                    && filterCommands.contains(builtinFilterCommand)) {
                filterCommand = builtinFilterCommand;
            }
        }
        if (filterCommand != null) {
            filterCommandsByNameDotType.put(key, filterCommand);
        }
        return filterCommand;
    }
}