// matchers.rs

//

// Copyright 2019 Raphaël Gomès <rgomes@octobus.net>

//

// This software may be used and distributed according to the terms of the

// GNU General Public License version 2 or any later version.

//! Structs and types for matching files and directories.

use format_bytes::format_bytes;

use once_cell::sync::OnceCell;

use crate::{

    dirstate::dirs_multiset::{DirsChildrenMultiset, DirsMultiset},

    filepatterns::{

        build_single_regex, filter_subincludes, get_patterns_from_file,

    },

    utils::{

        files::{dir_ancestors, find_dirs},

        hg_path::{HgPath, HgPathBuf, HgPathError},

        Escaped,

    },

};

use crate::dirstate::status::IgnoreFnType;

use crate::filepatterns::normalize_path_bytes;

use std::collections::HashSet;

use std::fmt::{Display, Error, Formatter};

use std::path::{Path, PathBuf};

use std::{borrow::ToOwned, collections::BTreeSet};

#[derive(Debug, PartialEq)]

pub enum VisitChildrenSet {

    /// Don't visit anything

    Empty,

    /// Visit this directory and probably its children

    This,

    /// Only visit the children (both files and directories) if they

    /// are mentioned in this set. (empty set corresponds to [Empty])

    /// TODO Should we implement a `NonEmptyHashSet`?

    Set(HashSet<HgPathBuf>),

    /// Visit this directory and all subdirectories

    /// (you can stop asking about the children set)

    Recursive,

}

pub trait Matcher: core::fmt::Debug {

    /// Explicitly listed files

    fn file_set(&self) -> Option<&HashSet<HgPathBuf>>;

    /// Returns whether `filename` is in `file_set`

    fn exact_match(&self, filename: &HgPath) -> bool;

    /// Returns whether `filename` is matched by this matcher

    fn matches(&self, filename: &HgPath) -> bool;

    /// Decides whether a directory should be visited based on whether it

    /// has potential matches in it or one of its subdirectories, and

    /// potentially lists which subdirectories of that directory should be

    /// visited. This is based on the match's primary, included, and excluded

    /// patterns.

    ///

    /// # Example

    ///

    /// Assume matchers `['path:foo/bar', 'rootfilesin:qux']`, we would

    /// return the following values (assuming the implementation of

    /// visit_children_set is capable of recognizing this; some implementations

    /// are not).

    ///

    /// ```text

    /// ```ignore

    /// '' -> {'foo', 'qux'}

    /// 'baz' -> set()

    /// 'foo' -> {'bar'}

    /// // Ideally this would be `Recursive`, but since the prefix nature of

    /// // matchers is applied to the entire matcher, we have to downgrade this

    /// // to `This` due to the (yet to be implemented in Rust) non-prefix

    /// // `RootFilesIn'-kind matcher being mixed in.

    /// 'foo/bar' -> 'this'

    /// 'qux' -> 'this'

    /// ```

    /// # Important

    ///

    /// Most matchers do not know if they're representing files or

    /// directories. They see `['path:dir/f']` and don't know whether `f` is a

    /// file or a directory, so `visit_children_set('dir')` for most matchers

    /// will return `HashSet{ HgPath { "f" } }`, but if the matcher knows it's

    /// a file (like the yet to be implemented in Rust `ExactMatcher` does),

    /// it may return `VisitChildrenSet::This`.

    /// Do not rely on the return being a `HashSet` indicating that there are

    /// no files in this dir to investigate (or equivalently that if there are

    /// files to investigate in 'dir' that it will always return

    /// `VisitChildrenSet::This`).

    fn visit_children_set(&self, directory: &HgPath) -> VisitChildrenSet;

    /// Matcher will match everything and `files_set()` will be empty:

    /// optimization might be possible.

    fn matches_everything(&self) -> bool;

    /// Matcher will match exactly the files in `files_set()`: optimization

    /// might be possible.

    fn is_exact(&self) -> bool;

}

/// Matches everything.

///```

/// use hg::{ matchers::{Matcher, AlwaysMatcher}, utils::hg_path::HgPath };

///

/// let matcher = AlwaysMatcher;

///

/// assert_eq!(matcher.matches(HgPath::new(b"whatever")), true);

/// assert_eq!(matcher.matches(HgPath::new(b"b.txt")), true);

/// assert_eq!(matcher.matches(HgPath::new(b"main.c")), true);

/// assert_eq!(matcher.matches(HgPath::new(br"re:.*\.c$")), true);

/// ```

#[derive(Debug)]

pub struct AlwaysMatcher;

impl Matcher for AlwaysMatcher {

    fn file_set(&self) -> Option<&HashSet<HgPathBuf>> {

        None

    }

    fn exact_match(&self, _filename: &HgPath) -> bool {

        false

    }

    fn matches(&self, _filename: &HgPath) -> bool {

        true

    }

    fn visit_children_set(&self, _directory: &HgPath) -> VisitChildrenSet {

        VisitChildrenSet::Recursive

    }

    fn matches_everything(&self) -> bool {

        true

    }

    fn is_exact(&self) -> bool {

        false

    }

}

/// Matches nothing.

#[derive(Debug)]

pub struct NeverMatcher;

impl Matcher for NeverMatcher {

    fn file_set(&self) -> Option<&HashSet<HgPathBuf>> {

        None

    }

    fn exact_match(&self, _filename: &HgPath) -> bool {

        false

    }

    fn matches(&self, _filename: &HgPath) -> bool {

        false

    }

    fn visit_children_set(&self, _directory: &HgPath) -> VisitChildrenSet {

        VisitChildrenSet::Empty

    }

    fn matches_everything(&self) -> bool {

        false

    }

    fn is_exact(&self) -> bool {

        true

    }

}

/// Matches the input files exactly. They are interpreted as paths, not

/// patterns.

///

///```

/// use hg::{ matchers::{Matcher, FileMatcher}, utils::hg_path::{HgPath, HgPathBuf} };

///

/// let files = vec![HgPathBuf::from_bytes(b"a.txt"), HgPathBuf::from_bytes(br"re:.*\.c$")];

/// let matcher = FileMatcher::new(files).unwrap();

///

/// assert_eq!(matcher.matches(HgPath::new(b"a.txt")), true);

/// assert_eq!(matcher.matches(HgPath::new(b"b.txt")), false);

/// assert_eq!(matcher.matches(HgPath::new(b"main.c")), false);

/// assert_eq!(matcher.matches(HgPath::new(br"re:.*\.c$")), true);

/// ```

#[derive(Debug)]

pub struct FileMatcher {

    files: HashSet<HgPathBuf>,

    dirs: DirsMultiset,

    sorted_visitchildrenset_candidates: OnceCell<BTreeSet<HgPathBuf>>,

}

impl FileMatcher {

    pub fn new(files: Vec<HgPathBuf>) -> Result<Self, HgPathError> {

        let dirs = DirsMultiset::from_manifest(&files)?;

        Ok(Self {

            files: HashSet::from_iter(files),

            dirs,

            sorted_visitchildrenset_candidates: OnceCell::new(),

        })

    }

    fn inner_matches(&self, filename: &HgPath) -> bool {

        self.files.contains(filename.as_ref())

    }

}

impl Matcher for FileMatcher {

    fn file_set(&self) -> Option<&HashSet<HgPathBuf>> {

        Some(&self.files)

    }

    fn exact_match(&self, filename: &HgPath) -> bool {

        self.inner_matches(filename)

    }

    fn matches(&self, filename: &HgPath) -> bool {

        self.inner_matches(filename)

    }

    fn visit_children_set(&self, directory: &HgPath) -> VisitChildrenSet {

        if self.files.is_empty() || !self.dirs.contains(directory) {

            return VisitChildrenSet::Empty;

        }

        let compute_candidates = || -> BTreeSet<HgPathBuf> {

            let mut candidates: BTreeSet<HgPathBuf> =

                self.dirs.iter().cloned().collect();

            candidates.extend(self.files.iter().cloned());

            candidates.remove(HgPath::new(b""));

            candidates

        };

        let candidates =

            if directory.as_ref().is_empty() {

                compute_candidates()

            } else {

                let sorted_candidates = self

                    .sorted_visitchildrenset_candidates

                    .get_or_init(compute_candidates);

                let directory_bytes = directory.as_ref().as_bytes();

                let start: HgPathBuf =

                    format_bytes!(b"{}/", directory_bytes).into();

                let start_len = start.len();

                // `0` sorts after `/`

                let end = format_bytes!(b"{}0", directory_bytes).into();

                BTreeSet::from_iter(sorted_candidates.range(start..end).map(

                    |c| HgPathBuf::from_bytes(&c.as_bytes()[start_len..]),

                ))

            };

        // `self.dirs` includes all of the directories, recursively, so if

        // we're attempting to match 'foo/bar/baz.txt', it'll have '', 'foo',

        // 'foo/bar' in it. Thus we can safely ignore a candidate that has a

        // '/' in it, indicating it's for a subdir-of-a-subdir; the immediate

        // subdir will be in there without a slash.

        VisitChildrenSet::Set(

            candidates

                .into_iter()

                .filter_map(|c| {

                    if c.bytes().all(|b| *b != b'/') {

                        Some(c)

                    } else {

                        None

                    }

                })

                .collect(),

        )

    }

    fn matches_everything(&self) -> bool {

        false

    }

    fn is_exact(&self) -> bool {

        true

    }

}

/// Matches a set of (kind, pat, source) against a 'root' directory.

/// (Currently the 'root' directory is effectively always empty)

/// ```

/// use hg::{

///     matchers::{PatternMatcher, Matcher},

///     utils::hg_path::{HgPath, HgPathBuf}

/// };

/// use std::collections::HashSet;

/// use std::path::Path;

/// ///

/// let ignore_patterns : Vec<IgnorePattern> =

///     vec![IgnorePattern::new(PatternSyntax::Regexp, br".*\.c$", Path::new("")),

///          IgnorePattern::new(PatternSyntax::Path, b"foo/a", Path::new("")),

///          IgnorePattern::new(PatternSyntax::RelPath, b"b", Path::new("")),

///          IgnorePattern::new(PatternSyntax::Glob, b"*.h", Path::new("")),

///     ];

/// let matcher = PatternMatcher::new(ignore_patterns).unwrap();

/// ///

/// assert_eq!(matcher.matches(HgPath::new(b"main.c")), true); // matches re:.*\.c$

/// assert_eq!(matcher.matches(HgPath::new(b"b.txt")), false);

/// assert_eq!(matcher.matches(HgPath::new(b"foo/a")), true); // matches path:foo/a

/// assert_eq!(matcher.matches(HgPath::new(b"a")), false); // does not match path:b, since 'root' is 'foo'

/// assert_eq!(matcher.matches(HgPath::new(b"b")), true); // matches relpath:b, since 'root' is 'foo'

/// assert_eq!(matcher.matches(HgPath::new(b"lib.h")), true); // matches glob:*.h

/// assert_eq!(matcher.file_set().unwrap(),

///            &HashSet::from([HgPathBuf::from_bytes(b""), HgPathBuf::from_bytes(b"foo/a"),

///                            HgPathBuf::from_bytes(b""), HgPathBuf::from_bytes(b"b")]));

/// assert_eq!(matcher.exact_match(HgPath::new(b"foo/a")), true);

/// assert_eq!(matcher.exact_match(HgPath::new(b"b")), true);

/// assert_eq!(matcher.exact_match(HgPath::new(b"lib.h")), false); // exact matches are for (rel)path kinds

/// ```

pub struct PatternMatcher<'a> {

    patterns: Vec<u8>,

    match_fn: IgnoreFnType<'a>,

    /// Whether all the patterns match a prefix (i.e. recursively)

    prefix: bool,

    files: HashSet<HgPathBuf>,

    dirs_explicit: HashSet<HgPathBuf>,

    dirs: DirsMultiset,

}

impl core::fmt::Debug for PatternMatcher<'_> {

    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {

        f.debug_struct("PatternMatcher")

            .field("patterns", &String::from_utf8_lossy(&self.patterns))

            .field("prefix", &self.prefix)

            .field("files", &self.files)

            .field("dirs", &self.dirs)

            .finish()

    }

}

impl<'a> PatternMatcher<'a> {

    pub fn new(ignore_patterns: Vec<IgnorePattern>) -> PatternResult<Self> {

        let RootsDirsAndParents {

            roots,

            dirs: dirs_explicit,

            parents,

        } = roots_dirs_and_parents(&ignore_patterns)?;

        let files = roots;

        let dirs = parents;

        let files: HashSet<HgPathBuf> = HashSet::from_iter(files);

        let prefix = ignore_patterns.iter().all(|k| {

            matches!(k.syntax, PatternSyntax::Path | PatternSyntax::RelPath)

        });

        let (patterns, match_fn) = build_match(ignore_patterns, b"$")?;

        Ok(Self {

            patterns,

            match_fn,

            prefix,

            files,

            dirs,

            dirs_explicit,

        })

    }

}

impl<'a> Matcher for PatternMatcher<'a> {

    fn file_set(&self) -> Option<&HashSet<HgPathBuf>> {

        Some(&self.files)

    }

    fn exact_match(&self, filename: &HgPath) -> bool {

        self.files.contains(filename)

    }

    fn matches(&self, filename: &HgPath) -> bool {

        if self.files.contains(filename) {

            return true;

        }

        (self.match_fn)(filename)

    }

    fn visit_children_set(&self, directory: &HgPath) -> VisitChildrenSet {

        if self.prefix && self.files.contains(directory) {

            return VisitChildrenSet::Recursive;

        }

        if self.dirs.contains(directory) {

            return VisitChildrenSet::This;

        }

        if dir_ancestors(directory).any(|parent_dir| {

            self.files.contains(parent_dir)

                || self.dirs_explicit.contains(parent_dir)

        }) {

            VisitChildrenSet::This

        } else {

            VisitChildrenSet::Empty

        }

    }

    fn matches_everything(&self) -> bool {

        false

    }

    fn is_exact(&self) -> bool {

        false

    }

}

/// Matches files that are included in the ignore rules.

/// ```

/// use hg::{

///     matchers::{IncludeMatcher, Matcher},

///     utils::hg_path::HgPath

/// };

/// use std::path::Path;

/// ///

/// let ignore_patterns =

/// vec![IgnorePattern::new(PatternSyntax::RootGlob, b"this*", Path::new(""))];

/// let matcher = IncludeMatcher::new(ignore_patterns).unwrap();

/// ///

/// assert_eq!(matcher.matches(HgPath::new(b"testing")), false);

/// assert_eq!(matcher.matches(HgPath::new(b"this should work")), true);

/// assert_eq!(matcher.matches(HgPath::new(b"this also")), true);

/// assert_eq!(matcher.matches(HgPath::new(b"but not this")), false);

/// ///

/// let ignore_patterns =

/// vec![IgnorePattern::new(PatternSyntax::RootFilesIn, b"dir/subdir", Path::new(""))];

/// let matcher = IncludeMatcher::new(ignore_patterns).unwrap();

/// ///

/// assert!(!matcher.matches(HgPath::new(b"file")));

/// assert!(!matcher.matches(HgPath::new(b"dir/file")));

/// assert!(matcher.matches(HgPath::new(b"dir/subdir/file")));

/// assert!(!matcher.matches(HgPath::new(b"dir/subdir/subsubdir/file")));

/// ```

pub struct IncludeMatcher<'a> {

    patterns: Vec<u8>,

    match_fn: IgnoreFnType<'a>,

    /// Whether all the patterns match a prefix (i.e. recursively)

    prefix: bool,

    roots: HashSet<HgPathBuf>,

    dirs: HashSet<HgPathBuf>,

    parents: DirsMultiset,

}

impl core::fmt::Debug for IncludeMatcher<'_> {

    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {

        f.debug_struct("IncludeMatcher")

            .field("patterns", &String::from_utf8_lossy(&self.patterns))

            .field("prefix", &self.prefix)

            .field("roots", &self.roots)

            .field("dirs", &self.dirs)

            .field("parents", &self.parents)

            .finish()

    }

}

impl<'a> Matcher for IncludeMatcher<'a> {

    fn file_set(&self) -> Option<&HashSet<HgPathBuf>> {

        None

    }

    fn exact_match(&self, _filename: &HgPath) -> bool {

        false

    }

    fn matches(&self, filename: &HgPath) -> bool {

        (self.match_fn)(filename)

    }

    fn visit_children_set(&self, directory: &HgPath) -> VisitChildrenSet {

        let dir = directory;

        if self.prefix && self.roots.contains(dir) {

            return VisitChildrenSet::Recursive;

        }

        if self.roots.contains(HgPath::new(b""))

            || self.roots.contains(dir)

            || self.dirs.contains(dir)

            || find_dirs(dir).any(|parent_dir| self.roots.contains(parent_dir))

        {

            return VisitChildrenSet::This;

        }

        if self.parents.contains(dir.as_ref()) {

            let multiset = self.get_all_parents_children();

            if let Some(children) = multiset.get(dir) {

                return VisitChildrenSet::Set(

                    children.iter().map(HgPathBuf::from).collect(),

                );

            }

        }

        VisitChildrenSet::Empty

    }

    fn matches_everything(&self) -> bool {

        false

    }

    fn is_exact(&self) -> bool {

        false

    }

}

/// The union of multiple matchers. Will match if any of the matchers match.

#[derive(Debug)]

pub struct UnionMatcher {

    matchers: Vec<Box<dyn Matcher + Sync>>,

}

impl Matcher for UnionMatcher {

    fn file_set(&self) -> Option<&HashSet<HgPathBuf>> {

        None

    }