/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */
package org.apache.maven.impl;

import java.io.File;
import java.nio.file.FileSystem;
import java.nio.file.Path;
import java.nio.file.PathMatcher;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

/**
 * Determines whether a path is selected according to include/exclude patterns.
 * The pathnames used for method parameters will be relative to some base directory
 * and use {@code '/'} as separator, regardless of the hosting operating system.
 *
 * <h2>Syntax</h2>
 * If a pattern contains the {@code ':'} character and the prefix before is longer than 1 character,
 * then that pattern is given verbatim to {@link FileSystem#getPathMatcher(String)}, which interprets
 * the part before {@code ':'} as the syntax (usually {@code "glob"} or {@code "regex"}).
 * If a pattern does not contain the {@code ':'} character, or if the prefix is one character long
 * (interpreted as a Windows drive), then the syntax defaults to a reproduction of the Maven 3 behavior.
 * This is implemented as the {@code "glob"} syntax with the following modifications:
 *
 * <ul>
 *   <li>The platform-specific separator ({@code '\\'} on Windows) is replaced by {@code '/'}.
 *       Note that it means that the backslash cannot be used for escaping characters.</li>
 *   <li>Trailing {@code "/"} is completed as {@code "/**"}.</li>
 *   <li>The {@code "**"} wildcard means "0 or more directories" instead of "1 or more directories".
 *       This is implemented by adding variants of the pattern without the {@code "**"} wildcard.</li>
 *   <li>Bracket characters [ ] and { } are escaped.</li>
 *   <li>On Unix only, the escape character {@code '\\'} is itself escaped.</li>
 * </ul>
 *
 * If above changes are not desired, put an explicit {@code "glob:"} prefix before the pattern.
 * Note that putting such a prefix is recommended anyway for better performances.
 *
 * @author Benjamin Bentmann
 * @author Martin Desruisseaux
 *
 * @see java.nio.file.FileSystem#getPathMatcher(String)
 */
public class PathSelector implements PathMatcher {
    /**
     * Patterns which should be excluded by default, like <abbr>SCM</abbr> files.
     *
     * <p><b>Source:</b> this list is copied from {@code plexus-utils-4.0.2} (released in
     * September 23, 2024), class {@code org.codehaus.plexus.util.AbstractScanner}.</p>
     */
    private static final List<String> DEFAULT_EXCLUDES = List.of(
            // Miscellaneous typical temporary files
            "**/*~",
            "**/#*#",
            "**/.#*",
            "**/%*%",
            "**/._*",

            // CVS
            "**/CVS",
            "**/CVS/**",
            "**/.cvsignore",

            // RCS
            "**/RCS",
            "**/RCS/**",

            // SCCS
            "**/SCCS",
            "**/SCCS/**",

            // Visual SourceSafe
            "**/vssver.scc",

            // MKS
            "**/project.pj",

            // Subversion
            "**/.svn",
            "**/.svn/**",

            // Arch
            "**/.arch-ids",
            "**/.arch-ids/**",

            // Bazaar
            "**/.bzr",
            "**/.bzr/**",

            // SurroundSCM
            "**/.MySCMServerInfo",

            // Mac
            "**/.DS_Store",

            // Serena Dimensions Version 10
            "**/.metadata",
            "**/.metadata/**",

            // Mercurial
            "**/.hg",
            "**/.hg/**",

            // git
            "**/.git",
            "**/.git/**",
            "**/.gitignore",

            // BitKeeper
            "**/BitKeeper",
            "**/BitKeeper/**",
            "**/ChangeSet",
            "**/ChangeSet/**",

            // darcs
            "**/_darcs",
            "**/_darcs/**",
            "**/.darcsrepo",
            "**/.darcsrepo/**",
            "**/-darcs-backup*",
            "**/.darcs-temp-mail");

    /**
     * Maximum number of characters of the prefix before {@code ':'} for handling as a Maven syntax.
     */
    private static final int MAVEN_SYNTAX_THRESHOLD = 1;

    /**
     * The default syntax to use if none was specified. Note that when this default syntax is applied,
     * the user-provided pattern get some changes as documented in class Javadoc.
     */
    private static final String DEFAULT_SYNTAX = "glob:";

    /**
     * Characters having a special meaning in the glob syntax.
     *
     * @see FileSystem#getPathMatcher(String)
     */
    private static final String SPECIAL_CHARACTERS = "*?[]{}\\";

    /**
     * A path matcher which accepts all files.
     *
     * @see #simplify()
     */
    private static final PathMatcher INCLUDES_ALL = (path) -> true;

    /**
     * String representations of the normalized include filters.
     * Each pattern shall be prefixed by its syntax, which is {@value #DEFAULT_SYNTAX} by default.
     *
     * @see #toString()
     */
    private final String[] includePatterns;

    /**
     * String representations of the normalized exclude filters.
     * Each pattern shall be prefixed by its syntax, which is {@value #DEFAULT_SYNTAX} by default.
     * This array may be longer or shorter than the user-supplied excludes, depending on whether
     * default excludes have been added and whether some unnecessary excludes have been omitted.
     *
     * @see #toString()
     */
    private final String[] excludePatterns;

    /**
     * The matcher for includes. The length of this array is equal to {@link #includePatterns} array length.
     */
    private final PathMatcher[] includes;

    /**
     * The matcher for excludes. The length of this array is equal to {@link #excludePatterns} array length.
     */
    private final PathMatcher[] excludes;

    /**
     * The matcher for all directories to include. This array includes the parents of all those directories,
     * because they need to be accepted before we can walk to the sub-directories.
     * This is an optimization for skipping whole directories when possible.
     */
    private final PathMatcher[] dirIncludes;

    /**
     * The matcher for directories to exclude. This array does <em>not</em> include the parent directories,
     * because they may contain other sub-trees that need to be included.
     * This is an optimization for skipping whole directories when possible.
     */
    private final PathMatcher[] dirExcludes;

    /**
     * The base directory. All files will be relativized to that directory before to be matched.
     */
    private final Path baseDirectory;

    /**
     * Creates a new selector from the given includes and excludes.
     *
     * @param directory the base directory of the files to filter
     * @param includes the patterns of the files to include, or null or empty for including all files
     * @param excludes the patterns of the files to exclude, or null or empty for no exclusion
     * @param useDefaultExcludes whether to augment the excludes with a default set of <abbr>SCM</abbr> patterns
     */
    public PathSelector(
            Path directory, Collection<String> includes, Collection<String> excludes, boolean useDefaultExcludes) {
        includePatterns = normalizePatterns(includes, false);
        excludePatterns = normalizePatterns(effectiveExcludes(excludes, includePatterns, useDefaultExcludes), true);
        baseDirectory = directory;
        FileSystem system = directory.getFileSystem();
        this.includes = matchers(system, includePatterns);
        this.excludes = matchers(system, excludePatterns);
        dirIncludes = matchers(system, directoryPatterns(includePatterns, false));
        dirExcludes = matchers(system, directoryPatterns(excludePatterns, true));
    }

    /**
     * Returns the given array of excludes, optionally expanded with a default set of excludes,
     * then with unnecessary excludes omitted. An unnecessary exclude is an exclude which will never
     * match a file because there is no include which would accept a file that could match the exclude.
     * For example, if the only include is {@code "*.java"}, then the <code>"**&sol;project.pj"</code>,
     * <code>"**&sol;.DS_Store"</code> and other excludes will never match a file and can be omitted.
     * Because the list of {@linkplain #DEFAULT_EXCLUDES default excludes} contains many elements,
     * removing unnecessary excludes can reduce a lot the number of matches tested on each source file.
     *
     * <h4>Implementation note</h4>
     * The removal of unnecessary excludes is done on a best effort basis. The current implementation
     * compares only the prefixes and suffixes of each pattern, keeping the pattern in case of doubt.
     * This is not bad, but it does not remove all unnecessary patterns. It would be possible to do
     * better in the future if benchmarking suggests that it would be worth the effort.
     *
     * @param excludes the user-specified excludes, potentially not yet converted to glob syntax
     * @param includes the include patterns converted to glob syntax
     * @param useDefaultExcludes whether to expand user exclude with the set of default excludes
     * @return the potentially expanded or reduced set of excludes to use
     */
    private static Collection<String> effectiveExcludes(
            Collection<String> excludes, final String[] includes, final boolean useDefaultExcludes) {
        if (excludes == null || excludes.isEmpty()) {
            if (useDefaultExcludes) {
                excludes = new ArrayList<>(DEFAULT_EXCLUDES);
            } else {
                return List.of();
            }
        } else {
            excludes = new ArrayList<>(excludes);
            if (useDefaultExcludes) {
                excludes.addAll(DEFAULT_EXCLUDES);
            }
        }
        /*
         * Get the prefixes and suffixes of all includes, stopping at the first special character.
         * Redundant prefixes and suffixes are omitted.
         */
        var prefixes = new String[includes.length];
        var suffixes = new String[includes.length];
        for (int i = 0; i < includes.length; i++) {
            String include = includes[i];
            if (!include.startsWith(DEFAULT_SYNTAX)) {
                return excludes; // Do not filter if at least one pattern is too complicated.
            }
            include = include.substring(DEFAULT_SYNTAX.length());
            prefixes[i] = prefixOrSuffix(include, false);
            suffixes[i] = prefixOrSuffix(include, true);
        }
        prefixes = sortByLength(prefixes, false);
        suffixes = sortByLength(suffixes, true);
        /*
         * Keep only the exclude which start with one of the prefixes and end with one of the suffixes.
         * Note that a prefix or suffix may be the empty string, which match everything.
         */
        final Iterator<String> it = excludes.iterator();
        nextExclude:
        while (it.hasNext()) {
            final String exclude = it.next();
            final int s = exclude.indexOf(':');
            if (s <= MAVEN_SYNTAX_THRESHOLD || exclude.startsWith(DEFAULT_SYNTAX)) {
                if (cannotMatch(exclude, prefixes, false) || cannotMatch(exclude, suffixes, true)) {
                    it.remove();
                }
            }
        }
        return excludes;
    }

    /**
     * Returns the maximal amount of ordinary characters at the beginning or end of the given pattern.
     * The prefix or suffix stops at the first {@linkplain #SPECIAL_CHARACTERS special character}.
     *
     * @param include the pattern for which to get a prefix or suffix without special character
     * @param suffix {@code false} if a prefix is desired, or {@code true} if a suffix is desired
     */
    private static String prefixOrSuffix(final String include, boolean suffix) {
        int s = suffix ? -1 : include.length();
        for (int i = SPECIAL_CHARACTERS.length(); --i >= 0; ) {
            char c = SPECIAL_CHARACTERS.charAt(i);
            if (suffix) {
                s = Math.max(s, include.lastIndexOf(c));
            } else {
                int p = include.indexOf(c);
                if (p >= 0 && p < s) {
                    s = p;
                }
            }
        }
        return suffix ? include.substring(s + 1) : include.substring(0, s);
    }

    /**
     * Returns {@code true} if the given exclude cannot match any include patterns.
     * In case of doubt, returns {@code false}.
     *
     * @param exclude the exclude pattern to test
     * @param fragments the prefixes or suffixes (fragments without special characters) of the includes
     * @param suffix {@code false} if the specified fragments are prefixes, {@code true} if they are suffixes
     * @return {@code true} if it is certain that the exclude pattern cannot match, or {@code false} in case of doubt
     */
    private static boolean cannotMatch(String exclude, final String[] fragments, final boolean suffix) {
        exclude = prefixOrSuffix(exclude, suffix);
        for (String fragment : fragments) {
            int fg = fragment.length();
            int ex = exclude.length();
            int length = Math.min(fg, ex);
            if (suffix) {
                fg -= length;
                ex -= length;
            } else {
                fg = 0;
                ex = 0;
            }
            if (exclude.regionMatches(ex, fragment, fg, length)) {
                return false;
            }
        }
        return true;
    }

    /**
     * Sorts the given patterns by their length. The main intent is to have the empty string first,
     * while will cause the loops testing for prefixes and suffixes to stop almost immediately.
     * Short prefixes or suffixes are also more likely to be matched.
     *
     * @param fragments the fragments to sort in-place
     * @param suffix {@code false} if the specified fragments are prefixes, {@code true} if they are suffixes
     * @return the given array, or a smaller array if some fragments were discarded because redundant
     */
    private static String[] sortByLength(final String[] fragments, final boolean suffix) {
        Arrays.sort(fragments, (s1, s2) -> s1.length() - s2.length());
        int count = 0;
        /*
         * Simplify the array of prefixes or suffixes by removing all redundant elements.
         * An element is redundant if there is a shorter prefix or suffix with the same characters.
         */
        nextBase:
        for (String fragment : fragments) {
            for (int i = count; --i >= 0; ) {
                String base = fragments[i];
                if (suffix ? fragment.endsWith(base) : fragment.startsWith(base)) {
                    continue nextBase; // Skip this fragment
                }
            }
            fragments[count++] = fragment;
        }
        return (fragments.length == count) ? fragments : Arrays.copyOf(fragments, count);
    }

    /**
     * Returns the given array of patterns with path separator normalized to {@code '/'}.
     * Null or empty patterns are ignored, and duplications are removed.
     *
     * @param patterns the patterns to normalize
     * @param excludes whether the patterns are exclude patterns
     * @return normalized patterns without null, empty or duplicated patterns
     */
    private static String[] normalizePatterns(final Collection<String> patterns, final boolean excludes) {
        if (patterns == null || patterns.isEmpty()) {
            return new String[0];
        }
        // TODO: use `LinkedHashSet.newLinkedHashSet(int)` instead with JDK19.
        final var normalized = new LinkedHashSet<String>(patterns.size());
        for (String pattern : patterns) {
            if (pattern != null && !pattern.isEmpty()) {
                if (pattern.indexOf(':') <= MAVEN_SYNTAX_THRESHOLD) {
                    pattern = pattern.replace(File.separatorChar, '/');
                    if (pattern.endsWith("/")) {
                        pattern += "**";
                    }
                    // Following are okay only when "**" means "0 or more directories".
                    while (pattern.endsWith("/**/**")) {
                        pattern = pattern.substring(0, pattern.length() - 3);
                    }
                    while (pattern.startsWith("**/**/")) {
                        pattern = pattern.substring(3);
                    }
                    pattern = pattern.replace("/**/**/", "/**/");
                    pattern = pattern.replace("\\", "\\\\")
                            .replace("[", "\\[")
                            .replace("]", "\\]")
                            .replace("{", "\\{")
                            .replace("}", "\\}");
                    normalized.add(DEFAULT_SYNTAX + pattern);
                    /*
                     * If the pattern starts or ends with "**", Java GLOB expects a directory level at
                     * that location while Maven seems to consider that "**" can mean "no directory".
                     * Add another pattern for reproducing this effect.
                     */
                    addPatternsWithOneDirRemoved(normalized, pattern, 0);
                } else {
                    normalized.add(pattern);
                }
            }
        }
        return simplify(normalized, excludes);
    }

    /**
     * Adds all variants of the given pattern with {@code **} removed.
     * This is used for simulating the Maven behavior where {@code "**} may match zero directory.
     * Tests suggest that we need an explicit GLOB pattern with no {@code "**"} for matching an absence of directory.
     *
     * @param patterns where to add the derived patterns
     * @param pattern  the pattern for which to add derived forms, without the "glob:" syntax prefix
     * @param end      should be 0 (reserved for recursive invocations of this method)
     */
    private static void addPatternsWithOneDirRemoved(final Set<String> patterns, final String pattern, int end) {
        final int length = pattern.length();
        int start;
        while ((start = pattern.indexOf("**", end)) >= 0) {
            end = start + 2; // 2 is the length of "**".
            if (end < length) {
                if (pattern.charAt(end) != '/') {
                    continue;
                }
                if (start == 0) {
                    end++; // Ommit the leading slash if there is nothing before it.
                }
            }
            if (start > 0 && pattern.charAt(--start) != '/') {
                continue;
            }
            String reduced = pattern.substring(0, start) + pattern.substring(end);
            patterns.add(DEFAULT_SYNTAX + reduced);
            addPatternsWithOneDirRemoved(patterns, reduced, start);
        }
    }

    /**
     * Applies some heuristic rules for simplifying the set of patterns,
     * then returns the patterns as an array.
     *
     * @param patterns the patterns to simplify and return asarray
     * @param excludes whether the patterns are exclude patterns
     * @return the set content as an array, after simplification
     */
    private static String[] simplify(Set<String> patterns, boolean excludes) {
        /*
         * If the "**" pattern is present, it makes all other patterns useless.
         * In the case of include patterns, an empty set means to include everything.
         */
        if (patterns.remove("**")) {
            patterns.clear();
            if (excludes) {
                patterns.add("**");
            }
        }
        return patterns.toArray(String[]::new);
    }

    /**
     * Eventually adds the parent directory of the given patterns, without duplicated values.
     * The patterns given to this method should have been normalized.
     *
     * @param patterns the normalized include or exclude patterns
     * @param excludes whether the patterns are exclude patterns
     * @return pattens of directories to include or exclude
     */
    private static String[] directoryPatterns(final String[] patterns, final boolean excludes) {
        // TODO: use `LinkedHashSet.newLinkedHashSet(int)` instead with JDK19.
        final var directories = new LinkedHashSet<String>(patterns.length);
        for (String pattern : patterns) {
            if (pattern.startsWith(DEFAULT_SYNTAX)) {
                if (excludes) {
                    if (pattern.endsWith("/**")) {
                        directories.add(pattern.substring(0, pattern.length() - 3));
                    }
                } else {
                    int s = pattern.indexOf(':');
                    if (pattern.regionMatches(++s, "**/", 0, 3)) {
                        s = pattern.indexOf('/', s + 3);
                        if (s < 0) {
                            return new String[0]; // Pattern is "**", so we need to accept everything.
                        }
                        directories.add(pattern.substring(0, s));
                    }
                }
            }
        }
        return simplify(directories, excludes);
    }

    /**
     * Creates the path matchers for the given patterns.
     * The syntax (usually {@value #DEFAULT_SYNTAX}) must be specified for each pattern.
     */
    private static PathMatcher[] matchers(final FileSystem fs, final String[] patterns) {
        final var matchers = new PathMatcher[patterns.length];
        for (int i = 0; i < patterns.length; i++) {
            matchers[i] = fs.getPathMatcher(patterns[i]);
        }
        return matchers;
    }

    /**
     * {@return a potentially simpler matcher equivalent to this matcher}.
     */
    @SuppressWarnings("checkstyle:MissingSwitchDefault")
    public PathMatcher simplify() {
        if (excludes.length == 0) {
            switch (includes.length) {
                case 0:
                    return INCLUDES_ALL;
                case 1:
                    return includes[0];
            }
        }
        return this;
    }

    /**
     * Determines whether a path is selected.
     * This is true if the given file matches an include pattern and no exclude pattern.
     *
     * @param path the pathname to test, must not be {@code null}
     * @return {@code true} if the given path is selected, {@code false} otherwise
     */
    @Override
    public boolean matches(Path path) {
        path = baseDirectory.relativize(path);
        return (includes.length == 0 || isMatched(path, includes))
                && (excludes.length == 0 || !isMatched(path, excludes));
    }

    /**
     * {@return whether the given file matches according to one of the given matchers}.
     */
    private static boolean isMatched(Path path, PathMatcher[] matchers) {
        for (PathMatcher matcher : matchers) {
            if (matcher.matches(path)) {
                return true;
            }
        }
        return false;
    }

    /**
     * Determines whether a directory could contain selected paths.
     *
     * @param directory the directory pathname to test, must not be {@code null}
     * @return {@code true} if the given directory might contain selected paths, {@code false} if the
     *         directory will definitively not contain selected paths
     */
    public boolean couldHoldSelected(Path directory) {
        if (baseDirectory.equals(directory)) {
            return true;
        }
        directory = baseDirectory.relativize(directory);
        return (dirIncludes.length == 0 || isMatched(directory, dirIncludes))
                && (dirExcludes.length == 0 || !isMatched(directory, dirExcludes));
    }

    /**
     * Appends the elements of the given array in the given buffer.
     * This is a helper method for {@link #toString()} implementations.
     *
     * @param buffer the buffer to add the elements to
     * @param label label identifying the array of elements to add
     * @param patterns the elements to append, or {@code null} if none
     */
    private static void append(StringBuilder buffer, String label, String[] patterns) {
        buffer.append(label).append(": [");
        if (patterns != null) {
            for (int i = 0; i < patterns.length; i++) {
                if (i != 0) {
                    buffer.append(", ");
                }
                buffer.append(patterns[i]);
            }
        }
        buffer.append(']');
    }

    /**
     * {@return a string representation for logging purposes}.
     */
    @Override
    public String toString() {
        var buffer = new StringBuilder();
        append(buffer, "includes", includePatterns);
        append(buffer.append(", "), "excludes", excludePatterns);
        return buffer.toString();
    }
}
