use std::{fmt, num::TryFromIntError, str::Chars};

#[derive(Debug)]
pub struct InvalidGlobError;
impl fmt::Display for InvalidGlobError {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.write_str("invalid glob")
    }
}
impl From<TryFromIntError> for InvalidGlobError {
    fn from(_: TryFromIntError) -> Self {
        Self
    }
}

enum Op {
    Slice { from: u16, to: u16 },
    Separator,
    Skip { count: u16 },
    Many,
    ManyComponents,
    AnyWithinRanges { from: u16, to: u16 },
    ExceptWithinRanges { from: u16, to: u16 },
    SubPatternGroup { len: u16 },
    SubPattern { len: u16 },
}

#[derive(Default)]
pub struct Glob {
    texts: String,
    ops: Vec<Op>,
}

impl Glob {
    pub fn compile(&mut self, pattern: &str) -> Result<(), InvalidGlobError> {
        self.texts.clear();
        self.ops.clear();

        match self.compile_recursive(pattern.chars()) {
            Ok(rest) if rest.as_str().is_empty() => Ok(()),
            _ => {
                self.texts.clear();
                self.ops.clear();
                Err(InvalidGlobError)
            }
        }
    }

    fn compile_recursive<'a>(
        &mut self,
        mut pattern: Chars<'a>,
    ) -> Result<Chars<'a>, InvalidGlobError> {
        let mut start_ops_index = self.ops.len();
        loop {
            let previous_state = pattern.clone();
            match pattern.next() {
                None => break,
                Some('?') => match self.ops[start_ops_index..].last_mut() {
                    Some(Op::Skip { count }) => *count += 1,
                    _ => self.ops.push(Op::Skip { count: 1 }),
                },
                Some('*') => {
                    let previous_state = pattern.clone();
                    match pattern.next() {
                        Some('*') => {
                            match self.ops.last() {
                                None | Some(Op::Separator) => (),
                                _ => return Err(InvalidGlobError),
                            }

                            let previous_state = pattern.clone();
                            match pattern.next() {
                                None => {
                                    pattern = previous_state;
                                    self.ops.push(Op::ManyComponents);
                                }
                                Some('/') => self.ops.push(Op::ManyComponents),
                                _ => return Err(InvalidGlobError),
                            }
                        }
                        _ => {
                            pattern = previous_state;
                            self.ops.push(Op::Many);
                        }
                    }
                }
                Some('[') => {
                    let previous_state = pattern.clone();
                    let inverse = match pattern.next() {
                        Some('!') => true,
                        _ => {
                            pattern = previous_state;
                            false
                        }
                    };
                    let from = self.texts.len().try_into()?;
                    loop {
                        let from = match pattern.next() {
                            None => return Err(InvalidGlobError),
                            Some(']') => break,
                            Some(c) => c,
                        };
                        let previous_state = pattern.clone();
                        let to = match pattern.next() {
                            Some('-') => {
                                let to = match pattern.next() {
                                    None | Some(']') => return Err(InvalidGlobError),
                                    Some(b) => b,
                                };
                                if to < from {
                                    return Err(InvalidGlobError);
                                }
                                to
                            }
                            _ => {
                                pattern = previous_state;
                                from
                            }
                        };

                        self.texts.push(from);
                        self.texts.push(to);
                    }
                    let to = self.texts.len().try_into()?;
                    if inverse {
                        self.ops.push(Op::ExceptWithinRanges { from, to })
                    } else {
                        self.ops.push(Op::AnyWithinRanges { from, to })
                    }
                }
                Some(']') => return Err(InvalidGlobError),
                Some('{') => {
                    let fix_index = self.ops.len();
                    self.ops.push(Op::SubPatternGroup { len: 0 });

                    loop {
                        let fix_index = self.ops.len();
                        self.ops.push(Op::SubPattern { len: 0 });

                        pattern = self.compile_recursive(pattern)?;

                        let ops_count = self.ops.len();
                        match &mut self.ops[fix_index] {
                            Op::SubPattern { len } => {
                                *len = (ops_count - fix_index - 1).try_into()?;
                            }
                            _ => unreachable!(),
                        }

                        match pattern.next() {
                            Some('}') => break,
                            Some(',') => continue,
                            _ => return Err(InvalidGlobError),
                        }
                    }

                    let ops_count = self.ops.len();
                    match &mut self.ops[fix_index] {
                        Op::SubPatternGroup { len } => {
                            *len = (ops_count - fix_index - 1).try_into()?;
                        }
                        _ => unreachable!(),
                    }

                    start_ops_index = self.ops.len();
                }
                Some('}' | ',') => return Ok(previous_state),
                Some('/') => self.ops.push(Op::Separator),
                Some(c) => match self.ops[start_ops_index..].last_mut() {
                    Some(Op::Slice { to, .. }) if *to == self.texts.len().try_into()? => {
                        self.texts.push(c);
                        *to = self.texts.len().try_into()?;
                    }
                    _ => {
                        let from = self.texts.len().try_into()?;
                        self.texts.push(c);
                        let to = self.texts.len().try_into()?;
                        self.ops.push(Op::Slice { from, to });
                    }
                },
            }
        }

        Ok(pattern)
    }

    pub fn matches(&self, path: &str) -> bool {
        matches_recursive(&self.ops, &self.texts, path.chars(), &Continuation::None)
    }
}

enum Continuation<'this, 'ops> {
    None,
    Next(&'ops [Op], &'this Continuation<'this, 'ops>),
}

fn matches_recursive<'data, 'cont>(
    mut ops: &'data [Op],
    texts: &str,
    mut path: Chars,
    continuation: &'cont Continuation<'cont, 'data>,
) -> bool {
    'op_loop: loop {
        let op = match ops.split_first() {
            Some((op, rest)) => {
                ops = rest;
                op
            }
            None => match continuation {
                Continuation::None => return path.next().is_none(),
                Continuation::Next(ops, continuation) => {
                    return matches_recursive(ops, texts, path, continuation)
                }
            },
        };

        match op {
            &Op::Slice { from, to } => {
                let prefix = &texts[(from as usize)..(to as usize)];
                match path.as_str().strip_prefix(prefix) {
                    Some(rest) => path = rest.chars(),
                    None => return false,
                }
            }
            Op::Separator => match path.next() {
                Some(c) if std::path::is_separator(c) => (),
                _ => return false,
            },
            &Op::Skip { count } => {
                for _ in 0..count {
                    match path.next() {
                        Some(c) if !std::path::is_separator(c) => (),
                        _ => return false,
                    }
                }
            }
            Op::Many => loop {
                if matches_recursive(ops, texts, path.clone(), continuation) {
                    return true;
                }
                match path.next() {
                    Some(c) if !std::path::is_separator(c) => (),
                    _ => return false,
                }
            },
            Op::ManyComponents => loop {
                if matches_recursive(ops, texts, path.clone(), continuation) {
                    return true;
                }
                if !path.any(std::path::is_separator) {
                    return false;
                }
            },
            &Op::AnyWithinRanges { from, to } => {
                let c = match path.next() {
                    Some(c) => c,
                    None => return false,
                };
                let mut ranges = texts[from as usize..to as usize].chars();
                while let Some(from) = ranges.next() {
                    let to = ranges.next().unwrap();
                    if from <= c && c <= to {
                        continue 'op_loop;
                    }
                }
                return false;
            }
            &Op::ExceptWithinRanges { from, to } => {
                let c = match path.next() {
                    Some(c) => c,
                    None => return false,
                };
                let mut ranges = texts[from as usize..to as usize].chars();
                while let Some(from) = ranges.next() {
                    let to = ranges.next().unwrap();
                    if c < from || to < c {
                        continue 'op_loop;
                    }
                }
                return false;
            }
            &Op::SubPatternGroup { len } => {
                let (mut ops, jump) = ops.split_at(len as _);
                while !ops.is_empty() {
                    let len = match ops[0] {
                        Op::SubPattern { len } => len as usize,
                        _ => unreachable!(),
                    };
                    ops = &ops[1..];
                    let continuation = Continuation::Next(jump, continuation);
                    if matches_recursive(&ops[..len], texts, path.clone(), &continuation) {
                        return true;
                    }
                    ops = &ops[len..];
                }
                return false;
            }
            Op::SubPattern { .. } => unreachable!(),
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn compile() {
        let mut glob = Glob::default();

        assert!(glob.compile("").is_ok());
        assert!(glob.compile("abc").is_ok());
        assert!(glob.compile("a?c").is_ok());
        assert!(glob.compile("a[A-Z]c").is_ok());
        assert!(glob.compile("a[!0-9]c").is_ok());

        assert!(glob.compile("a*c").is_ok());
        assert!(glob.compile("a*/").is_ok());
        assert!(glob.compile("a*/c").is_ok());
        assert!(glob.compile("a*[0-9]/c").is_ok());
        assert!(glob.compile("a*bx*cy*d").is_ok());

        assert!(glob.compile("**").is_ok());
        assert!(glob.compile("/**").is_ok());
        assert!(glob.compile("**/").is_ok());
        assert!(glob.compile("a/**/").is_ok());
        assert!(glob.compile("a/**/c").is_ok());
        assert!(glob.compile("a/**c").is_err());
        assert!(glob.compile("a**/c").is_err());

        assert!(glob.compile("a{b,c}d").is_ok());
        assert!(glob.compile("a*{b,c}d").is_ok());
        assert!(glob.compile("a*{b*,c}d").is_ok());
        assert!(glob.compile("}").is_err());
        assert!(glob.compile(",").is_err());
    }

    #[test]
    fn matches() {
        fn assert_glob(glob: &mut Glob, expected: bool, pattern: &str, path: &str) {
            assert!(
                glob.compile(pattern).is_ok(),
                "invalid glob pattern '{}'",
                pattern,
            );
            assert_eq!(
                expected,
                glob.matches(path),
                "'{}' did {} match pattern '{}'",
                path,
                if expected { " not" } else { "" },
                pattern,
            );
        }

        let mut glob = Glob::default();

        assert_glob(&mut glob, true, "", "");
        assert_glob(&mut glob, true, "abc", "abc");
        assert_glob(&mut glob, false, "ab", "abc");
        assert_glob(&mut glob, true, "a?c", "abc");
        assert_glob(&mut glob, false, "a??", "a/c");
        assert_glob(&mut glob, true, "a[A-Z]c", "aBc");
        assert_glob(&mut glob, false, "a[A-Z]c", "abc");
        assert_glob(&mut glob, true, "a[!0-9A-CD-FGH]c", "abc");

        assert_glob(&mut glob, true, "*", "");
        assert_glob(&mut glob, true, "*", "a");
        assert_glob(&mut glob, true, "*", "abc");
        assert_glob(&mut glob, true, "a*c", "ac");
        assert_glob(&mut glob, true, "a*c", "abc");
        assert_glob(&mut glob, true, "a*c", "abbbc");
        assert_glob(&mut glob, true, "a*/", "abc/");
        assert_glob(&mut glob, true, "a*/c", "a/c");
        assert_glob(&mut glob, true, "a*/c", "abbb/c");
        assert_glob(&mut glob, true, "a*[0-9]/c", "abbb5/c");
        assert_glob(&mut glob, false, "a*c", "a/c");
        assert_glob(&mut glob, true, "a*bx*cy*d", "a00bx000cy0000d");

        assert_glob(&mut glob, false, "a/**/c", "");
        assert_glob(&mut glob, true, "a/**/c", "a/c");
        assert_glob(&mut glob, true, "a/**/c", "a/b/c");
        assert_glob(&mut glob, true, "a/**/c", "a/bb/bbb/c");
        assert_glob(&mut glob, true, "a/**/c", "a/a/bb/bbb/c");
        assert_glob(&mut glob, true, "**/c", "c");
        assert_glob(&mut glob, true, "**/c", "a/c");
        assert_glob(&mut glob, false, "**/c", "ac");
        assert_glob(&mut glob, false, "**/c", "a/bc");
        assert_glob(&mut glob, true, "**/c", "ab/c");
        assert_glob(&mut glob, true, "**/c", "a/b/c");

        assert_glob(&mut glob, true, "a{b,c}d", "abd");
        assert_glob(&mut glob, true, "a{b,c}d", "acd");
        assert_glob(&mut glob, true, "a*{b,c}d", "aaabd");
        assert_glob(&mut glob, true, "a*{b,c}d", "abbbd");
        assert_glob(&mut glob, true, "a*{b*,c}d", "acdbbczzcd");
        assert_glob(&mut glob, true, "a{b,c*}d", "aczd");
        assert_glob(&mut glob, true, "a*{b,c*}d", "acdbczzzd");

        assert_glob(&mut glob, false, "**/*.{a,b,cd}", "");
        assert_glob(&mut glob, true, "**/*.{a,b,cd}", "n.a");
        assert_glob(&mut glob, true, "**/*.{a,b,cd}", "n.b");
        assert_glob(&mut glob, true, "**/*.{a,b,cd}", "n.cd");
        assert_glob(&mut glob, true, "**/*.{a,b,cd}", "m/n.a");
        assert_glob(&mut glob, true, "**/*.{a,b,cd}", "m/n.b");
        assert_glob(&mut glob, true, "**/*.{a,b,cd}", "m/n.cd");
        assert_glob(&mut glob, true, "**/*.{a,b,cd}", "m/n/p.a");
        assert_glob(&mut glob, true, "**/*.{a,b,cd}", "m/n/p.b");
        assert_glob(&mut glob, true, "**/*.{a,b,cd}", "m/n/p.cd");
        assert_glob(&mut glob, false, "**/*.{a,b,cd}", "n.x");
        assert_glob(&mut glob, false, "**/*.{a,b,cd}", "m/n.x");
        assert_glob(&mut glob, false, "**/*.{a,b,cd}", "m/n/p.x");

        assert_glob(&mut glob, false, "**/*.{é,ç}", "");
        assert_glob(&mut glob, true, "**/*.{é,ç}", "p.é");
        assert_glob(&mut glob, true, "**/*.{é,ç}", "p.ç");
        assert_glob(&mut glob, true, "**/*.{é,ç}", "n/p.é");
        assert_glob(&mut glob, true, "**/*.{é,ç}", "n/p.ç");
        assert_glob(&mut glob, true, "**/*.{é,ç}", "m/n/p.é");
        assert_glob(&mut glob, true, "**/*.{é,ç}", "m/n/p.ç");
        assert_glob(&mut glob, false, "**/*.{é,ç}", "p.e");
        assert_glob(&mut glob, false, "**/*.{é,ç}", "p.c");
    }
}