GitIgnore.cs

// Copyright (c) Microsoft.  All Rights Reserved.  Licensed under the Apache License, Version 2.0.  See License.txt in the project root for license information.

using System;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Diagnostics;
using System.IO;
using System.Text;

namespace Microsoft.Build.Tasks.Git
{
    internal sealed class GitIgnore
    {
        internal sealed class PatternGroup
        {
            /// <summary>
            /// Directory of the .gitignore file that defines the pattern.
            /// Full posix slash terminated path.
            /// </summary>
            public readonly string ContainingDirectory;

            public readonly ImmutableArray<Pattern> Patterns;

            public readonly PatternGroup Parent;

            public PatternGroup(PatternGroup parent, string containingDirectory, ImmutableArray<Pattern> patterns)
            {
                Debug.Assert(PathUtils.IsPosixPath(containingDirectory));
                Debug.Assert(PathUtils.HasTrailingSlash(containingDirectory));

                Parent = parent;
                ContainingDirectory = containingDirectory;
                Patterns = patterns;
            }
        }

        internal readonly struct Pattern
        {
            public readonly PatternFlags Flags;
            public readonly string Glob;

            public Pattern(string glob,  PatternFlags flags)
            {
                Debug.Assert(glob != null);

                Glob = glob;
                Flags = flags;
            }

            public bool IsDirectoryPattern => (Flags & PatternFlags.DirectoryPattern) != 0;
            public bool IsFullPathPattern => (Flags & PatternFlags.FullPath) != 0;
            public bool IsNegative => (Flags & PatternFlags.Negative) != 0;

            public override string ToString() 
                => $"{(IsNegative ? "!" : "")}{Glob}{(IsDirectoryPattern ? " <dir>" : "")}{(IsFullPathPattern ? " <path>" : "")}";
        }

        [Flags]
        internal enum PatternFlags
        {
            None = 0,
            Negative = 1,
            DirectoryPattern = 2,
            FullPath = 4,
        }

        private const string GitIgnoreFileName = ".gitignore";

        /// <summary>
        /// Full posix slash terminated path.
        /// </summary>
        private readonly string _workingDirectory;
        private readonly string _workingDirectoryNoSlash;

        private readonly bool _ignoreCase;

        /// <summary>
        /// Maps full posix slash-terminated directory name to a pattern group.
        /// </summary>
        private readonly Dictionary<string, PatternGroup> _patternGroups;

        private readonly PatternGroup _root;

        internal GitIgnore(PatternGroup root, string workingDirectory, bool ignoreCase)
        {
            Debug.Assert(PathUtils.IsPosixPath(workingDirectory));
            Debug.Assert(PathUtils.HasTrailingSlash(workingDirectory));

            _ignoreCase = ignoreCase;
            _workingDirectory = workingDirectory;
            _workingDirectoryNoSlash = PathUtils.TrimTrailingSlash(workingDirectory);
            _root = root;
            _patternGroups = new Dictionary<string, PatternGroup>();
        }

        private StringComparison PathComparison
            => _ignoreCase ? StringComparison.OrdinalIgnoreCase : StringComparison.Ordinal;

        /// <summary>
        /// Checks if the specified file path is ignored.
        /// </summary>
        /// <param name="fullPath">Normalized path.</param>
        /// <returns>True if the path is ignored, fale if it is not, null if it is outside of the working directory.</returns>
        public bool? IsNormalizedFilePathIgnored(string fullPath)
        {
            if (!PathUtils.IsAbsolute(fullPath))
            {
                throw new ArgumentException("Path must be absolute", nameof(fullPath));
            }

            if (PathUtils.HasTrailingDirectorySeparator(fullPath))
            {
                throw new ArgumentException("Path must be a file path", nameof(fullPath));
            }

            return IsPathIgnored(fullPath, isDirectoryPath: false);
        }

        /// <summary>
        /// Checks if the specified path is ignored.
        /// </summary>
        /// <param name="fullPath">Full path.</param>
        /// <returns>True if the path is ignored, fale if it is not, null if it is outside of the working directory.</returns>
        public bool? IsPathIgnored(string fullPath)
        {
            if (!PathUtils.IsAbsolute(fullPath))
            {
                throw new ArgumentException("Path must be absolute", nameof(fullPath));
            }

            var fullPathNoSlash = PathUtils.TrimTrailingDirectorySeparator(Path.GetFullPath(fullPath));

            // git uses the FS case-sensitivity for checking directory existence:
            bool isDirectoryPath = PathUtils.HasTrailingDirectorySeparator(fullPath) || Directory.Exists(fullPath); 

            if (isDirectoryPath && fullPathNoSlash.Equals(_workingDirectoryNoSlash, PathComparison))
            {
                return false;
            }

            return IsPathIgnored(fullPathNoSlash, isDirectoryPath);
        }

        private bool? IsPathIgnored(string normalizedPath, bool isDirectoryPath)
        {
            Debug.Assert(PathUtils.IsAbsolute(normalizedPath));
            Debug.Assert(!PathUtils.HasTrailingDirectorySeparator(normalizedPath));

            normalizedPath = PathUtils.ToPosixPath(normalizedPath);

            // paths outside of working directory:
            if (!normalizedPath.StartsWith(_workingDirectory, PathComparison))
            {
                return null;
            }

            static void splitPath(string fullPath, out string directoryWithSlash, out string fileName)
            {
                int i = fullPath.LastIndexOf('/', fullPath.Length - (PathUtils.HasTrailingSlash(fullPath) ? 2 : 1));
                if (i < 0)
                {
                    directoryWithSlash = null;
                    fileName = fullPath;
                }
                else
                {
                    directoryWithSlash = fullPath.Substring(0, i + 1);
                    fileName = fullPath.Substring(i + 1);
                }
            }

            splitPath(normalizedPath, out var directory, out var fileName);
            Debug.Assert(directory != null);

            // Default patterns can't be overriden by a negative pattern:
            if (fileName.Equals(".git", PathComparison))
            {
                return true;
            }

            var groups = new List<PatternGroup>();

            while (true)
            {
                bool isIgnored = false;

                // Visit groups in reverse order.
                // Patterns specified closer to the target file override those specified above.
                for (var patternGroup = GetPatternGroup(directory); patternGroup != null; patternGroup = patternGroup.Parent)
                {
                    groups.Add(patternGroup);
                }

                for (int i = groups.Count - 1; i >= 0; i--)
                {
                    var patternGroup = groups[i];

                    if (!normalizedPath.StartsWith(patternGroup.ContainingDirectory, PathComparison))
                    {
                        continue;
                    }

                    var relativePath = normalizedPath.Substring(patternGroup.ContainingDirectory.Length);

                    foreach (var pattern in patternGroup.Patterns)
                    {
                        // If a pattern is matched as ignored only look for a negative pattern that matches as well.
                        // If a pattern is not matched then skip negative patterns.
                        if (isIgnored != pattern.IsNegative)
                        {
                            continue;
                        }

                        if (pattern.IsDirectoryPattern && !isDirectoryPath)
                        {
                            continue;
                        }

                        var matchPath = pattern.IsFullPathPattern ? relativePath : fileName;
                        if (Glob.IsMatch(pattern.Glob, matchPath, _ignoreCase, matchWildCardWithDirectorySeparator: false))
                        {
                            // TODO: optimize negative pattern lookup (once we match, do we need to continue matching?)
                            isIgnored = !pattern.IsNegative;
                        }
                    }
                }

                if (isIgnored)
                {
                    return true;
                }

                splitPath(directory, out directory, out fileName);
                if (directory == null || !directory.StartsWith(_workingDirectory, PathComparison))
                {
                    return false;
                }

                isDirectoryPath = true;
                groups.Clear();
            }
        }

        private PatternGroup GetPatternGroup(string directory)
        {
            if (_patternGroups.TryGetValue(directory, out var group))
            {
                return group;
            }

            PatternGroup parent;
            if (directory.Equals(_workingDirectory, PathComparison))
            {
                parent = _root;
            }
            else
            {
                parent = GetPatternGroup(PathUtils.ToPosixDirectoryPath(Path.GetDirectoryName(PathUtils.TrimTrailingSlash(directory))));
            }

            group = LoadFromFile(Path.Combine(directory, GitIgnoreFileName), parent) ?? parent;

            _patternGroups.Add(directory, group);
            return group;
        }

        /// <exception cref="IOException"/>
        /// <exception cref="ArgumentException"><paramref name="path"/> is invalid</exception>
        internal static PatternGroup LoadFromFile(string path, PatternGroup parent)
        {
            // See https://git-scm.com/docs/gitignore#_pattern_format

            if (!File.Exists(path))
            {
                return null;
            }

            StreamReader reader;
            try
            {
                reader = File.OpenText(path);
            }
            catch (Exception e) when (e is FileNotFoundException || e is DirectoryNotFoundException)
            {
                return null;
            }

            var reusableBuffer = new StringBuilder();

            var directory = PathUtils.ToPosixDirectoryPath(Path.GetFullPath(Path.GetDirectoryName(path)));
            var patterns = ImmutableArray.CreateBuilder<Pattern>();

            using (reader)
            {
                while (true)
                {
                    string line = reader.ReadLine();
                    if (line == null)
                    {
                        break;
                    }

                    if (TryParsePattern(line, reusableBuffer, out var glob, out var flags))
                    {
                        patterns.Add(new Pattern(glob, flags));
                    }
                }
            }

            if (patterns.Count == 0)
            {
                return null;
            }

            return new PatternGroup(parent, directory, patterns.ToImmutable());
        }

        internal static bool TryParsePattern(string line, StringBuilder reusableBuffer, out string glob, out PatternFlags flags)
        {
            glob = null;
            flags = PatternFlags.None;
            
            // Trailing spaces are ignored unless '\'-escaped.
            // Leading spaces are significant.
            // Other whitespace (\t, \v, \f) is significant. 
            int e = line.Length - 1;
            while (e >= 0 && line[e] == ' ')
            {
                e--;
            }

            e++;

            // Skip blank line.
            if (e == 0)
            {
                return false;
            }

            // put trailing space back if escaped:
            if (e < line.Length && line[e] == ' ' && line[e - 1] == '\\')
            {
                e++;
            }

            int s = 0;

            // Skip comment.
            if (line[s] == '#')
            {
                return false;
            }

            // Pattern negation.
            if (line[s] == '!')
            {
                flags |= PatternFlags.Negative;
                s++;
            }

            if (s == e)
            {
                return false;
            }

            if (line[e - 1] == '/')
            {
                flags |= PatternFlags.DirectoryPattern;
                e--;
            }

            if (s == e)
            {
                return false;
            }

            if (line.IndexOf('/', s, e - s) >= 0)
            {
                flags |= PatternFlags.FullPath;
            }

            if (line[s] == '/')
            {
                s++;
            }

            if (s == e)
            {
                return false;
            }

            int escape = line.IndexOf('\\', s, e - s);
            if (escape < 0)
            {
                glob = line.Substring(s, e - s);
                return true;
            }

            reusableBuffer.Clear();
            reusableBuffer.Append(line, s, escape - s);

            int i = escape;
            while (i < e)
            {
                var c = line[i++];
                if (c == '\\' && i < e)
                {
                    c = line[i++];
                }

                reusableBuffer.Append(c);
            }

            glob = reusableBuffer.ToString();
            return true;
        }
    }
}