sub-strs 0.29.2

/*
==--==--==--==--==--==--==--==--==--==--==--==--==--==--==--==--

sub-strs

Copyright (C) 2019-2023  Anonymous

There are several releases over multiple years,
they are listed as ranges, such as: "2019-2023".

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License
along with this program.  If not, see <https://www.gnu.org/licenses/>.

::--::--::--::--::--::--::--::--::--::--::--::--::--::--::--::--
*/

//! # Glob

use {
    alloc::{
        borrow::Cow,
        collections::BTreeMap,
        string::String,
        vec::Vec,
    },
    core::{
        fmt::{self, Display, Formatter},
        str::FromStr,
    },
};

use crate::Error;

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

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

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

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

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

impl<'a> Part<'a> {

    /// # Parses parts
    fn parse<'b, F>(mut s: &'b str, str_fn: F) -> Vec<Self> where F: Fn(&'b str) -> Cow<'a, str> {
        let mut result = alloc::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_fn(&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_fn(s)));
                    }
                    break;
                },
            };
        }

        result
    }

}

impl<'a> Part<'a> {

    /// # Parses a `&str`
    fn parse_str(s: &'a str) -> Vec<Self> {
        Part::parse(s, |s| Cow::from(s))
    }

    /// # Parses a [`String`][r://String]
    ///
    /// [r://String]: https://doc.rust-lang.org/std/string/struct.String.html
    fn parse_string(s: String) -> Vec<Self> {
        Part::parse(&s, |s| Cow::from(String::from(s)))
    }

}

/// # 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, Ord, PartialOrd)]
pub struct Glob<'a> {
    parts: Vec<Part<'a>>,
}

impl<'a> Glob<'a> {

    /// # Makes new instance
    const fn new(parts: Vec<Part<'a>>) -> Self {
        Self {
            parts,
        }
    }

    /// # 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) => match map.get_mut(&part_idx) {
                        Some(SubStr { fixed, idx: sub_idx }) => match char_count == 0 || s.chars().take(char_count).count() >= char_count {
                            true => if *fixed && part_idx + 1 == self.parts.len() && sub.len() + *sub_idx != s.len() {
                                return false;
                            },
                            false => 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<BTreeMap<usize, SubStr>> {
        let mut result = BTreeMap::new();

        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) -> core::result::Result<Self, Self::Err> {
        Ok(Self::from(String::from(s)))
    }

}

impl Display for Glob<'_> {

    fn fmt(&self, f: &mut Formatter) -> core::result::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(())
    }

}