// License: see LICENSE file at root directory of `master` branch

//! # Glob

use std::{
    borrow::Cow,
    collections::HashMap,
    fmt::{self, Display, Formatter},
    io::{self, Error},
    str::FromStr,
};

const ANY: char = '*';
const ONE_CHAR: char = '?';

/// # Parts of a `&str`
#[derive(Debug, Eq, PartialEq, Hash)]
enum Part<'a> {

    /// # A string
    Str(Cow<'a, str>),

    /// # Any (`*`)
    Any,

    /// # One character (`?`)
    OneChar,
}

macro_rules! str_to_cow {
    // Do NOT remove the casting -- we're using some dangerous tool in a safe language
    ($s: expr) => { Cow::from($s as &str) }
}

macro_rules! clone_str_to_cow {
    // Do NOT remove the casting -- we're using some dangerous tool in a safe language
    ($s: expr) => { Cow::from(String::from($s as &str)) }
}

macro_rules! parse_parts {
    ($s: ident, $str_handler: ident) => {{
        let mut result = vec![];
        loop {
            match $s.find(|c| match c { self::ANY | self::ONE_CHAR => true, _ => false }) {
                Some(i) => {
                    if i > 0 {
                        result.push(Part::Str($str_handler!(&$s[..i])));
                    }
                    match $s.as_bytes()[i] as char {
                        self::ANY => if result.last() != Some(&Part::Any) {
                            result.push(Part::Any);
                        },
                        self::ONE_CHAR => result.push(Part::OneChar),
                        _ => {},
                    };
                    if i + 1 == $s.len() {
                        break;
                    }
                    $s = &$s[i + 1..];
                },
                None => {
                    if $s.is_empty() == false {
                        result.push(Part::Str($str_handler!($s)));
                    }
                    break;
                },
            };
        }

        result
    }}
}

impl<'a> Part<'a> {

    /// # Parses a `&str`
    fn parse_str(mut s: &'a str) -> Vec<Self> {
        parse_parts!(s, str_to_cow)
    }

    /// # Parses a [`String`][r://String]
    ///
    /// [r://String]: https://doc.rust-lang.org/std/string/struct.String.html
    fn parse_string(s: String) -> Vec<Self> {
        let mut s = s.as_str();
        parse_parts!(s, clone_str_to_cow)
    }

}

/// # Sub string, used in Glob::matches()
#[derive(Debug)]
struct SubStr {
    fixed: bool,
    idx: usize,
}

/// # Glob
///
/// This struct is used to find matches from a pattern string against some string.
///
/// The pattern string supports 2 special characters: `*` and `?`:
///
/// - `*`: matches any characters or nothing at all.
/// - `?`: matches one single character.
///
/// ## Notes
///
/// - The idea is inspired by <https://en.wikipedia.org/wiki/Glob_%28programming%29>, but this is _not_ an implementation of that or any other
///   specifications.
/// - Matches are _case sensitive_. If you want to ignore case, consider using [`to_lowercase()`][r://String/to_lowercase()] (or
///   [`to_uppercase()`][r://String/to_uppercase()]) on _both_ pattern and target string.
/// - [`Display`][r://Display] implementation prints _parsed_ pattern, not the original one.
/// - Implementations of `From<&'a str>` and `From<&'a String>` always borrow the source string.
/// - Implementations of `FromStr` and `From<String>` will _clone_ the source string.
///
/// ## Examples
///
/// <!-- NOTE: these examples are also *essential* tests, do NOT change or remove them. -->
///
/// ```
/// use sub_strs::Glob;
///
/// let g = Glob::from("*r?st.rs");
/// for s in &["rust.rs", "rEst.rs", "it's rust.rs"] {
///     assert!(g.matches(s));
/// }
/// for s in &["it's not Rust", "rest", "rust!.rs"] {
///     assert!(g.matches(s) == false);
/// }
/// ```
///
/// [r://String]: https://doc.rust-lang.org/std/string/struct.String.html
/// [r://String/to_lowercase()]: https://doc.rust-lang.org/std/string/struct.String.html#method.to_lowercase
/// [r://String/to_uppercase()]: https://doc.rust-lang.org/std/string/struct.String.html#method.to_uppercase
/// [r://Display]: https://doc.rust-lang.org/std/fmt/trait.Display.html
#[derive(Debug, Eq, PartialEq, Hash)]
pub struct Glob<'a> {
    parts: Vec<Part<'a>>,
    sub_str_count: usize,
}

impl<'a> Glob<'a> {

    /// # Makes new instance
    fn new(parts: Vec<Part<'a>>) -> Self {
        let sub_str_count = parts.iter().filter(|p| match p { Part::Str(_) => true, _ => false }).count();
        Self {
            parts,
            sub_str_count,
        }
    }

    /// # Checks if this glob matches a string
    pub fn matches<S>(&self, s: S) -> bool where S: AsRef<str> {
        let s = s.as_ref();

        if self.parts.is_empty() {
            return s.is_empty();
        }

        let mut map = match self.make_map(s) {
            Some(map) => map,
            None => return false,
        };
        loop {
            let mut char_count: usize = 0;
            for (part_idx, part) in self.parts.iter().enumerate() {
                match part {
                    Part::Any => {},
                    Part::OneChar => char_count += 1,
                    Part::Str(sub) => if char_count > 0 && s.chars().take(char_count).count() < char_count {
                        match map.get_mut(&part_idx) {
                            Some(SubStr { fixed, idx: sub_idx }) => match fixed {
                                true => return false,
                                false => match s[*sub_idx..].chars().next() {
                                    Some(c) => match s[*sub_idx + c.len_utf8()..].find(sub.as_ref()) {
                                        Some(i) => {
                                            *sub_idx = i;
                                            break;
                                        },
                                        None => return false,
                                    },
                                    None => return false,
                                },
                            },
                            // This is internal error
                            None => return false,
                        };
                    },
                };

                if part_idx + 1 == self.parts.len() {
                    return true;
                }
            }
        }
    }

    /// # Makes map
    fn make_map(&self, s: &str) -> Option<HashMap<usize, SubStr>> {
        let mut result = HashMap::with_capacity(self.sub_str_count);
        let mut dynamic = false;
        let mut idx = 0;
        for (part_idx, part) in self.parts.iter().enumerate() {
            match part {
                Part::Str(sub) => {
                    let fixed;
                    let sub_idx;
                    if part_idx == 0 {
                        match s.starts_with(sub.as_ref()) {
                            true => {
                                fixed = true;
                                sub_idx = 0;
                            },
                            false => return None,
                        };
                    } else if part_idx + 1 == self.parts.len() {
                        match s.ends_with(sub.as_ref()) {
                            true => {
                                fixed = true;
                                sub_idx = s.len() - sub.len();
                            },
                            false => return None,
                        };
                    } else {
                        fixed = dynamic == false;
                        sub_idx = match s[idx..].find(sub.as_ref()) {
                            Some(i) => {
                                idx = i + sub.len();
                                i
                            },
                            None => return None,
                        };
                    }
                    result.insert(part_idx, SubStr { fixed, idx: sub_idx });
                },
                Part::Any => dynamic = true,
                Part::OneChar => match s[idx..].chars().next() {
                    Some(c) => idx += c.len_utf8(),
                    None => return None,
                },
            };
        }

        Some(result)
    }

}

/// # Converts from a `&str` to [`Glob`][::Glob]
///
/// [::Glob]: struct.Glob.html
impl<'a> From<&'a str> for Glob<'a> {

    fn from(src: &'a str) -> Self {
        Self::new(Part::parse_str(src))
    }

}

/// # Converts from a [`&String`][r://String] to [`Glob`][::Glob]
///
/// [::Glob]: struct.Glob.html
/// [r://String]: https://doc.rust-lang.org/std/string/struct.String.html
impl<'a> From<&'a String> for Glob<'a> {

    fn from(src: &'a String) -> Self {
        Self::from(src.as_str())
    }

}

/// # Converts from a [`String`][r://String] to [`Glob`][::Glob]
///
/// [::Glob]: struct.Glob.html
/// [r://String]: https://doc.rust-lang.org/std/string/struct.String.html
impl From<String> for Glob<'_> {

    fn from(src: String) -> Self {
        Self::new(Part::parse_string(src))
    }

}

impl<'a> From<Cow<'a, str>> for Glob<'a> {

    fn from(s: Cow<'a, str>) -> Self {
        match s {
            Cow::Borrowed(s) => Self::from(s),
            Cow::Owned(s) => Self::from(s),
        }
    }

}

impl FromStr for Glob<'_> {

    type Err = Error;

    fn from_str(s: &str) -> io::Result<Self> {
        Ok(Self::from(String::from(s)))
    }

}

impl Display for Glob<'_> {

    fn fmt(&self, f: &mut Formatter) -> Result<(), fmt::Error> {
        use fmt::Write;

        for p in self.parts.iter() {
            match p {
                Part::Str(s) => f.write_str(s)?,
                Part::Any => f.write_char(ANY)?,
                Part::OneChar => f.write_char(ONE_CHAR)?,
            };
        }

        Ok(())
    }

}