// filepatterns.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.

//! Handling of Mercurial-specific patterns.

use crate::{

    pre_regex::PreRegex,

    utils::{

        files::{canonical_path, get_bytes_from_path, get_path_from_bytes},

        hg_path::{path_to_hg_path_buf, HgPathBuf, HgPathError},

        strings::SliceExt,

    },

    FastHashMap,

};

use lazy_static::lazy_static;

use regex::bytes::{NoExpand, Regex};

use std::mem;

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

use std::vec::Vec;

use std::{fmt, ops::Deref};

#[derive(Debug, derive_more::From)]

pub enum PatternError {

    #[from]

    Path(HgPathError),

    UnsupportedSyntax(String),

    UnsupportedSyntaxInFile(String, String, usize),

    TooLong(usize),

    #[from]

    IO(std::io::Error),

    /// Needed a pattern that can be turned into a regex but got one that

    /// can't. This should only happen through programmer error.

    NonRegexPattern(IgnorePattern),

}

impl fmt::Display for PatternError {

    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {

        match self {

            PatternError::UnsupportedSyntax(syntax) => {

                write!(f, "Unsupported syntax {}", syntax)

            }

            PatternError::UnsupportedSyntaxInFile(syntax, file_path, line) => {

                write!(

                    f,

                    "{}:{}: unsupported syntax {}",

                    file_path, line, syntax

                )

            }

            PatternError::TooLong(size) => {

                write!(f, "matcher pattern is too long ({} bytes)", size)

            }

            PatternError::IO(error) => error.fmt(f),

            PatternError::Path(error) => error.fmt(f),

            PatternError::NonRegexPattern(pattern) => {

                write!(f, "'{:?}' cannot be turned into a regex", pattern)

            }

        }

    }

}

lazy_static! {

    static ref RE_ESCAPE: Vec<Vec<u8>> = {

        let mut v: Vec<Vec<u8>> = (0..=255).map(|byte| vec![byte]).collect();

        let to_escape = b"()[]{}?*+-|^$\\.&~#\t\n\r\x0b\x0c";

        for byte in to_escape {

            v[*byte as usize].insert(0, b'\\');

        }

        v

    };

}

#[derive(Debug, Clone, PartialEq, Eq)]

pub enum PatternSyntax {

    /// A regular expression

    Regexp,

    /// Glob that matches at the front of the path

    RootGlob,

    /// Glob that matches at any suffix of the path (still anchored at

    /// slashes)

    Glob,

    /// a path relative to repository root, which is matched recursively

    Path,

    /// a single exact path relative to repository root

    FilePath,

    /// A path relative to cwd

    RelPath,

    /// an unrooted glob (*.rs matches Rust files in all dirs)

    RelGlob,

    /// A regexp that needn't match the start of a name

    RelRegexp,

    /// A path relative to repository root, which is matched non-recursively

    /// (will not match subdirectories)

    RootFilesIn,

    /// A file of patterns to read and include

    Include,

    /// A file of patterns to match against files under the same directory

    SubInclude,

    /// SubInclude with the result of parsing the included file

    ///

    /// Note: there is no ExpandedInclude because that expansion can be done

    /// in place by replacing the Include pattern by the included patterns.

    /// SubInclude requires more handling.

    ///

    /// Note: `Box` is used to minimize size impact on other enum variants

    ExpandedSubInclude(Box<SubInclude>),

}

/// A wildcard parsed from a glob

#[derive(Debug, Clone, Copy)]

enum GlobWildcard {

    /// `**/` matches any sequence of characters ending at a path

    /// component boundary

    AnyComponents,

    /// `*`: matches any sequence of characters within one path component

    AnyNonSlash,

    /// `**`: matches any sequence of characters including slashes

    Anything,

}

impl GlobWildcard {

    /// Optimization to simplify the regex prefixes for unrooted globs.

    /// It's unclear if this is worth it for performance, but it also has

    /// some cosmetic effect by making these regexes easier to understand.

    fn make_unrooted(wildcard: Option<GlobWildcard>) -> GlobWildcard {

        match wildcard {

            None => Self::AnyComponents,

            Some(Self::AnyComponents) => Self::AnyComponents,

            Some(Self::AnyNonSlash) => Self::Anything,

            Some(Self::Anything) => Self::Anything,

        }

    }

    fn to_re(self) -> PreRegex {

        match self {

            Self::AnyComponents => PreRegex::preceding_dir_components(),

            Self::AnyNonSlash => PreRegex::NonslashStar,

            Self::Anything => PreRegex::DotStar,

        }

    }

}

fn glob_parse_after_star(input: &mut &[u8]) -> GlobWildcard {

    if let Some((b'*', rest)) = input.split_first() {

        if let Some((b'/', rest)) = rest.split_first() {

            *input = rest;

            GlobWildcard::AnyComponents

        } else {

            *input = rest;

            GlobWildcard::Anything

        }

    } else {

        GlobWildcard::AnyNonSlash

    }

}

/// The result of glob to re conversion.

/// The start of the regular expression `start` is tracked

/// separately for a pattern simplification opportunity

/// (see `GlobWildcard::make_unrooted`)

pub struct GlobToRe {

    start: Option<GlobWildcard>,

    rest: Vec<PreRegex>,

}

impl GlobToRe {

    /// Convert to a regex. `rooted` specifies if the glob should match

    /// at the root of the repo (true), or anywhere in the repo (false)

    fn into_re(self, rooted: bool) -> PreRegex {

        let wildcard = if !rooted {

            Some(GlobWildcard::make_unrooted(self.start))

        } else {

            self.start

        };

        let mut res: Vec<_> =

            wildcard.into_iter().map(|x| x.to_re()).collect();

        res.extend(self.rest);

        PreRegex::Sequence(res)

    }

}

/// Transforms a glob pattern into a regex.

pub fn glob_to_re(pat: &[u8]) -> PatternResult<GlobToRe> {

    let mut start = None;

    let mut res: Vec<PreRegex> = vec![];

    let mut input = pat;

    let mut group_stack = vec![];

    let add_byte = |out: &mut Vec<PreRegex>, b: u8| match out.last_mut() {

        Some(PreRegex::Bytes(v)) => {

            v.push(b);

        }

        _ => out.push(PreRegex::Bytes(vec![b])),

    };

    while let Some((c, rest)) = input.split_first() {

        input = rest;

        match c {

            b'*' => {

                let wildcard = glob_parse_after_star(&mut input);

                if res.is_empty() && start.is_none() {

                    start = Some(wildcard)

                } else {

                    res.push(wildcard.to_re())

                }

            }

            b'?' => res.push(PreRegex::Dot),

            b'[' => {

                match input.iter().skip(1).position(|b| *b == b']') {

                    None => res.push(PreRegex::Byte(b'[')),

                    Some(end) => {

                        // Account for the one we skipped

                        let end = end + 1;

                        // TODO: parse charsets ourselves?

                        let mut class = vec![];

                        class.extend(b"[");

                        for (i, b) in input[..end].iter().enumerate() {

                            if *b == b'!' && i == 0 {

                                class.extend(b"^")

                            } else if *b == b'^' && i == 0 {

                                class.extend(b"\\^")

                            } else if *b == b'\\' {

                                class.extend(b"\\\\")

                            } else {

                                class.push(*b)

                            }

                        }

                        class.extend(b"]");

                        res.push(PreRegex::parse(&class)?);

                        input = &input[end + 1..];

                    }

                }

            }

            b'{' => {

                group_stack.push((mem::take(&mut res), vec![]));

            }

            b'}' if !group_stack.is_empty() => {

                let hir = PreRegex::Sequence(mem::take(&mut res));

                let (old_res, mut alt) = group_stack.pop().unwrap();

                alt.push(hir);

                res = old_res;

                res.push(PreRegex::Alternation(alt));

            }

            b',' if !group_stack.is_empty() => {

                let frame = group_stack.last_mut().unwrap();

                frame.1.push(PreRegex::Sequence(mem::take(&mut res)));

            }

            b'\\' => {

                let c = {

                    if let Some((c, rest)) = input.split_first() {

                        input = rest;

                        c

                    } else {

                        c

                    }

                };

                add_byte(&mut res, *c)

            }

            _ => add_byte(&mut res, *c),

        }

    }

    if !group_stack.is_empty() {

        return Err(PatternError::UnsupportedSyntax(

            "error: invalid glob, has unclosed alternation ('{')".to_string(),

        ));

    }

    Ok(GlobToRe { start, rest: res })

}

pub fn parse_pattern_syntax_kind(

    kind: &[u8],

) -> Result<PatternSyntax, PatternError> {

    match kind {

        b"re" => Ok(PatternSyntax::Regexp),

        b"path" => Ok(PatternSyntax::Path),

        b"filepath" => Ok(PatternSyntax::FilePath),

        b"relpath" => Ok(PatternSyntax::RelPath),

        b"rootfilesin" => Ok(PatternSyntax::RootFilesIn),

        b"relglob" => Ok(PatternSyntax::RelGlob),

        b"relre" => Ok(PatternSyntax::RelRegexp),

        b"glob" => Ok(PatternSyntax::Glob),

        b"rootglob" => Ok(PatternSyntax::RootGlob),

        b"include" => Ok(PatternSyntax::Include),

        b"subinclude" => Ok(PatternSyntax::SubInclude),

        _ => Err(PatternError::UnsupportedSyntax(

            String::from_utf8_lossy(kind).to_string(),

        )),

    }

}

lazy_static! {

    static ref FLAG_RE: Regex = Regex::new(r"^\(\?[aiLmsux]+\)").unwrap();

}

/// Extra path components to match at the end of the pattern

#[derive(Clone, Copy)]

pub enum GlobSuffix {

    /// `Empty` means the pattern only matches files, not directories,

    /// so the path needs to match exactly.

    Empty,

    /// `MoreComponents` means the pattern matches directories as well,

    /// so any path that has the pattern as a prefix, should match.

    MoreComponents,

}

impl GlobSuffix {

    pub fn to_re(self) -> PreRegex {

        match self {

            Self::Empty => PreRegex::Eof,

            Self::MoreComponents => PreRegex::SlashOrEof,

        }

    }

}

/// Builds the regex that corresponds to the given pattern.

/// If within a `syntax: regexp` context, returns the pattern,

/// otherwise, returns the corresponding regex.

fn _build_single_regex(

    entry: &IgnorePattern,

    glob_suffix: GlobSuffix,

) -> PatternResult<PreRegex> {

    let IgnorePattern {

        syntax, pattern, ..

    } = entry;

    if pattern.is_empty() {

        return Ok(PreRegex::Empty);

    }

    match syntax {

        PatternSyntax::Regexp => PreRegex::parse(pattern),

        PatternSyntax::RelRegexp => {

            // The `regex` crate accepts `**` while `re2` and Python's `re`

            // do not. Checking for `*` correctly triggers the same error all

            // engines.

            if pattern[0] == b'^'

                || pattern[0] == b'*'

                || pattern.starts_with(b".*")

            {

                return PreRegex::parse(pattern);

            }

            let re = match FLAG_RE.find(pattern) {

                Some(mat) => {

                    let s = mat.start();

                    let e = mat.end();

                    [

                        &b"(?"[..],

                        &pattern[s + 2..e - 1],

                        &b":"[..],

                        if pattern[e] == b'^'

                            || pattern[e] == b'*'

                            || pattern[e..].starts_with(b".*")

                        {

                            &b""[..]

                        } else {

                            &b".*"[..]

                        },

                        &pattern[e..],

                        &b")"[..],

                    ]

                    .concat()

                }

                None => [&b".*"[..], pattern].concat(),

            };

            PreRegex::parse(&re)

        }

        PatternSyntax::Path | PatternSyntax::RelPath => {

            if pattern == b"." {

                return Ok(PreRegex::Empty);

            }

            Ok(PreRegex::Sequence(vec![

                PreRegex::literal(pattern),

                GlobSuffix::MoreComponents.to_re(),

            ]))

        }

        PatternSyntax::RootFilesIn => {

            let re = if pattern == b"." {

                PreRegex::Empty

            } else {

                // Pattern is a directory name.

                let mut pattern = pattern.clone();

                pattern.push(b'/');

                PreRegex::Bytes(pattern)

            };

            // Anything after the pattern must be a non-directory.

            Ok(PreRegex::Sequence(vec![re, PreRegex::parse(b"[^/]+$")?]))

        }

        PatternSyntax::RelGlob => {

            let glob_re = glob_to_re(pattern)?;

            Ok(PreRegex::Sequence(vec![

                glob_re.into_re(false),

                glob_suffix.to_re(),

            ]))

        }

        PatternSyntax::Glob | PatternSyntax::RootGlob => {

            let glob_re = glob_to_re(pattern)?;

            Ok(PreRegex::Sequence(vec![

                glob_re.into_re(true),

                glob_suffix.to_re(),

            ]))

        }

        PatternSyntax::Include

        | PatternSyntax::SubInclude

        | PatternSyntax::ExpandedSubInclude(_)

        | PatternSyntax::FilePath => unreachable!(),

    }

}

const GLOB_SPECIAL_CHARACTERS: [u8; 7] =

    [b'*', b'?', b'[', b']', b'{', b'}', b'\\'];

/// TODO support other platforms

#[cfg(unix)]

pub fn normalize_path_bytes(bytes: &[u8]) -> Vec<u8> {

    if bytes.is_empty() {

        return b".".to_vec();

    }

    let sep = b'/';

    let mut initial_slashes = bytes.iter().take_while(|b| **b == sep).count();

    if initial_slashes > 2 {

        // POSIX allows one or two initial slashes, but treats three or more

        // as single slash.

        initial_slashes = 1;

    }

    let components = bytes

        .split(|b| *b == sep)

        .filter(|c| !(c.is_empty() || c == b"."))

        .fold(vec![], |mut acc, component| {

            if component != b".."

                || (initial_slashes == 0 && acc.is_empty())

                || (!acc.is_empty() && acc[acc.len() - 1] == b"..")

            {

                acc.push(component)

            } else if !acc.is_empty() {

                acc.pop();

            }

            acc

        });

    let mut new_bytes = components.join(&sep);

    if initial_slashes > 0 {

        let mut buf: Vec<_> = (0..initial_slashes).map(|_| sep).collect();

        buf.extend(new_bytes);

        new_bytes = buf;

    }

    if new_bytes.is_empty() {

        b".".to_vec()

    } else {

        new_bytes

    }

}

/// Controls whether we want the emitted regex to cover all cases

/// or just the cases that are not covered by optimized code paths.

#[derive(Debug, Clone, Copy)]

pub enum RegexCompleteness {

    /// `Complete` emits a regex that handles all files, including the ones

    /// that are typically handled by a different code path.

    /// This is used in `hg debugignorerhg -a` to avoid missing some rules.

    Complete,

    /// `ExcludeExactFiles` excludes the patterns that correspond to exact

    /// file matches. This is the normal behavior, and gives a potentially

    /// much smaller regex.

    ExcludeExactFiles,

}

impl RegexCompleteness {

    fn may_exclude_exact_files(self) -> bool {

        match self {

            Self::Complete => false,

            Self::ExcludeExactFiles => true,

        }

    }

}

/// Wrapper function to `_build_single_regex` that short-circuits 'exact' globs

/// that don't need to be transformed into a regex.

pub fn build_single_regex(

    entry: &IgnorePattern,

    glob_suffix: GlobSuffix,

    regex_config: RegexCompleteness,

) -> Result<Option<PreRegex>, PatternError> {

    let IgnorePattern {

        pattern, syntax, ..