// SPDX-FileCopyrightText: 2024 Aurélien Gâteau <mail@agateau.com>
//
// SPDX-License-Identifier: Apache-2.0

use std::fmt;

use lazy_regex::{regex, regex_find};
use tree_ds::prelude::*;

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Token {
    Group { header: String, quantifier: String },
    Literal { text: String, quantifier: String },
    Set { text: String, quantifier: String },
    Edge { symbol: String },
    Alternative,
}

impl Default for Token {
    fn default() -> Token {
        Token::Literal {
            text: "".into(),
            quantifier: "".into(),
        }
    }
}

impl Token {
    fn with_quantifier(&self, quantifier: &str) -> Self {
        match self {
            Token::Group { header, .. } => Token::Group {
                header: header.into(),
                quantifier: quantifier.into(),
            },
            Token::Literal { text, .. } => Token::Literal {
                text: text.into(),
                quantifier: quantifier.into(),
            },
            Token::Set { text, .. } => Token::Set {
                text: text.into(),
                quantifier: quantifier.into(),
            },
            _ => {
                panic!("Can't add quantifier to token type \"{}\"", self);
            }
        }
    }
}

impl fmt::Display for Token {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Token::Group { header, quantifier } => {
                write!(f, "G<{}><{}>", header, quantifier)
            }
            Token::Literal { text, quantifier } => {
                write!(f, "L<{}><{}>", text, quantifier)
            }
            Token::Set { text, quantifier } => {
                write!(f, "[{}]<{}>", text, quantifier)
            }
            Token::Edge { symbol } => {
                write!(f, "E{}", symbol)
            }
            Token::Alternative {} => {
                write!(f, "|")
            }
        }
    }
}

pub type RegexTree = Tree<AutomatedId, Token>;
pub type RegexNode = Node<AutomatedId, Token>;

/// Read the header of the group and return it as a string
/// `start` is the indice *after* the `(`
fn consume_group_header(pattern: &str, start: usize) -> anyhow::Result<(String, usize)> {
    let unfinished_group = || anyhow::anyhow!("Unfinished group");

    let mut end = start;
    let next = pattern.chars().nth(end).ok_or_else(unfinished_group)?;
    if next == '?' {
        end += 1;
        match pattern.chars().nth(end).ok_or_else(unfinished_group)? {
            ':' | '>' | '#' | '=' | '!' => end += 1,
            'P' => {
                let match_ =
                    regex_find!("^P<[^>]+>", &pattern[end..]).ok_or_else(unfinished_group)?;
                end += match_.len();
            }
            _ => {
                let rx = regex!("^[aiLmsux]+(-[imsx]+)?:");
                if let Some(match_) = rx.find(&pattern[end..]) {
                    end += match_.len();
                }
            } // TODO: (?aiLmsux)
        }
    }
    Ok((pattern[start..end].into(), end))
}

fn consume_quantifier(pattern: &str, idx: usize) -> anyhow::Result<(String, usize)> {
    let match_ = regex_find!("[+*]\\??|\\?|\\{[0-9]*,?[0-9]*}", &pattern[idx - 1..])
        .ok_or_else(|| anyhow::anyhow!("Invalid quantifier"))?;

    let end = idx - 1 + match_.len();

    let quantifier: String = pattern[idx - 1..end].into();
    Ok((quantifier, end))
}

/// Given a non-empty string, return a tuple of the string minus the last char, and the last char
/// Take into account escaped chars, so for "foo\\n" it returns "foo", "\\n"
///
fn split_last_char(text: &str) -> (Option<&str>, &str) {
    let len = text.len();
    assert!(len >= 1);

    if len == 1 {
        return (None, text);
    }
    let idx = if text.chars().nth(len - 2) == Some('\\') {
        len - 2
    } else {
        len - 1
    };
    if idx > 0 {
        (Some(&text[..idx]), &text[idx..])
    } else {
        (None, text)
    }
}

struct Builder<'a> {
    tree: &'a mut RegexTree,
    node_id_for_next_matcher: Option<AutomatedId>,
}

impl<'a> Builder<'a> {
    fn new(tree: &'a mut RegexTree) -> Self {
        Builder {
            tree,
            node_id_for_next_matcher: None,
        }
    }

    fn add_token(&mut self, parent_id: Option<&AutomatedId>, token: Token) -> AutomatedId {
        let node = RegexNode::new_with_auto_id(Some(token));
        let node_id = self.tree.add_node(node, parent_id).unwrap();
        self.node_id_for_next_matcher = Some(node_id);
        node_id
    }

    fn add_literal(&mut self, parent_id: Option<&AutomatedId>, text: &str) {
        self.add_token(
            parent_id,
            Token::Literal {
                text: text.into(),
                quantifier: "".into(),
            },
        );
    }

    fn add_set(&mut self, parent_id: Option<&AutomatedId>, text: &str) {
        self.add_token(
            parent_id,
            Token::Set {
                text: text.into(),
                quantifier: "".into(),
            },
        );
    }

    fn add_alternative(&mut self, parent_id: Option<&AutomatedId>) {
        self.add_token(parent_id, Token::Alternative);
    }

    fn add_edge(&mut self, parent_id: Option<&AutomatedId>, ch: char) {
        self.add_token(parent_id, Token::Edge { symbol: ch.into() });
    }

    fn add_group(&mut self, parent_id: Option<&AutomatedId>, header: &str) -> AutomatedId {
        self.add_token(
            parent_id,
            Token::Group {
                header: header.into(),
                quantifier: "".into(),
            },
        )
    }

    pub fn parse(&mut self, pattern: &str) -> anyhow::Result<()> {
        let mut text: String = String::new();
        let mut parent_id: AutomatedId = self.add_group(None, "");

        let mut inside_set = false;
        let mut escape_next = false;
        let mut idx = 0;
        while idx < pattern.len() {
            let ch = pattern.chars().nth(idx).unwrap();
            idx += 1;
            if !escape_next && ch == '\\' {
                escape_next = true;
                text.push(ch);
                continue;
            }

            if escape_next {
                text.push(ch);
                escape_next = false;
                continue;
            }

            if inside_set {
                if ch == ']' {
                    self.add_set(Some(&parent_id), &text);
                    text.clear();
                    inside_set = false;
                } else {
                    text.push(ch);
                }
                continue;
            }

            match ch {
                '[' => {
                    if !text.is_empty() {
                        self.add_literal(Some(&parent_id), &text);
                        text.clear();
                    }
                    inside_set = true;
                }
                '(' => {
                    if !text.is_empty() {
                        self.add_literal(Some(&parent_id), &text);
                        text.clear();
                    }
                    let (group_header, new_idx) = consume_group_header(pattern, idx)?;
                    idx = new_idx;
                    parent_id = self.add_group(Some(&parent_id), &group_header);
                }
                ')' => {
                    if !text.is_empty() {
                        self.add_literal(Some(&parent_id), &text);
                        text.clear();
                    }
                    let group_node = self.tree.get_node_by_id(&parent_id).unwrap();
                    self.node_id_for_next_matcher = Some(group_node.get_node_id());
                    parent_id = group_node
                        .get_parent_id()
                        .ok_or_else(|| anyhow::anyhow!("Unexpected end of group at row {}", idx))?;
                }
                '|' => {
                    if !text.is_empty() {
                        self.add_literal(Some(&parent_id), &text);
                        text.clear();
                    }
                    self.add_alternative(Some(&parent_id));
                }
                '^' | '$' => {
                    if !text.is_empty() {
                        self.add_literal(Some(&parent_id), &text);
                        text.clear();
                    }
                    self.add_edge(Some(&parent_id), ch);
                }
                '*' | '?' | '+' | '{' => {
                    if !text.is_empty() {
                        let (text_start, last_char) = split_last_char(&text);
                        if let Some(text_start) = text_start {
                            self.add_literal(Some(&parent_id), text_start);
                        }
                        self.add_literal(Some(&parent_id), last_char);
                        text.clear();
                    }
                    let (quantifier, new_idx) = consume_quantifier(pattern, idx)?;
                    idx = new_idx;

                    let node = self
                        .tree
                        .get_node_by_id(&self.node_id_for_next_matcher.unwrap())
                        .unwrap();

                    let token = node.get_value().unwrap().with_quantifier(&quantifier);

                    node.set_value(Some(token));
                }
                x => {
                    text.push(x);
                }
            }
        }
        if !text.is_empty() {
            self.add_literal(Some(&parent_id), &text);
        }
        Ok(())
    }
}

pub fn parse_regex(pattern: &str) -> anyhow::Result<RegexTree> {
    let mut tree = RegexTree::new(None);
    let mut builder = Builder::new(&mut tree);
    builder.parse(pattern)?;
    Ok(tree)
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::fs;
    use std::iter::zip;
    use std::path::{Path, PathBuf};

    use serde_json::Value;
    use yare::parameterized;

    fn get_fixtures_dir() -> PathBuf {
        let manifest_dir = Path::new(env!("CARGO_MANIFEST_DIR"));
        let path = manifest_dir.join("src").join("fixtures");
        if !path.exists() {
            panic!("Can't find fixtures dir");
        }
        path
    }

    fn get_fixture_path(name: &str) -> PathBuf {
        let fixtures_dir = get_fixtures_dir();
        let path = fixtures_dir.join(name);
        if !path.exists() {
            panic!("Can't find {name}");
        }
        path
    }

    struct Fixture {
        pattern: String,
        tree: RegexTree,
    }

    fn fill_tree(builder: &mut Builder, parent_id: Option<&AutomatedId>, value: &Value) -> () {
        match value {
            Value::String(x) => {
                if x == "|" {
                    builder.add_alternative(parent_id);
                } else {
                    builder.add_literal(parent_id, x);
                }
            }
            Value::Object(obj) => {
                let type_ = match obj.get("type") {
                    Some(x) => x.as_str().unwrap(),
                    None => "group".into(),
                };
                match type_ {
                    "set" => {
                        let text = obj["text"].as_str().unwrap();
                        let quantifier = match obj.get("quantifier") {
                            Some(x) => x.as_str().unwrap(),
                            None => "".into(),
                        };
                        builder.add_token(
                            parent_id,
                            Token::Set {
                                text: text.into(),
                                quantifier: quantifier.into(),
                            },
                        );
                    }
                    "group" => {
                        let header = match obj.get("header") {
                            Some(x) => x.as_str().unwrap(),
                            None => "".into(),
                        };
                        let children = obj["children"].as_array().unwrap();
                        let quantifier = match obj.get("quantifier") {
                            Some(x) => x.as_str().unwrap(),
                            None => "".into(),
                        };
                        let node_id = builder.add_token(
                            parent_id,
                            Token::Group {
                                header: header.into(),
                                quantifier: quantifier.into(),
                            },
                        );

                        for child in children {
                            fill_tree(builder, Some(&node_id), child);
                        }
                    }
                    "literal" => {
                        let text = obj["text"].as_str().unwrap();
                        let quantifier = obj["quantifier"].as_str().unwrap();
                        builder.add_token(
                            parent_id,
                            Token::Literal {
                                text: text.into(),
                                quantifier: quantifier.into(),
                            },
                        );
                    }
                    "edge" => {
                        let symbol = obj["symbol"].as_str().unwrap();
                        builder.add_token(
                            parent_id,
                            Token::Edge {
                                symbol: symbol.into(),
                            },
                        );
                    }
                    _ => {
                        panic!("Unknown type \"{}\"", type_);
                    }
                };
            }
            Value::Array(children) => {
                let node_id = builder.add_group(parent_id, "");
                for child in children {
                    fill_tree(builder, Some(&node_id), child);
                }
            }
            _ => {
                panic!("Unexpected value type {}", value);
            }
        }
    }

    fn load_fixture(path: &Path) -> anyhow::Result<Fixture> {
        let content = fs::read_to_string(path)?;

        let mut tree: RegexTree = Tree::new(None);
        let root: Value = serde_json::from_str(&content)?;
        let pattern = root["pattern"].as_str().unwrap().into();
        let json_tree: &Value = &root["tree"];

        let mut builder = Builder::new(&mut tree);
        fill_tree(&mut builder, None, json_tree);

        Ok(Fixture {
            pattern: pattern,
            tree: tree,
        })
    }

    #[parameterized(
        plain = { "plain.json" },
        sets = { "sets.json" },
        simple_group = { "simple_group.json" },
        nested = { "nested.json" },
        non_capture_group = { "non_capture_group.json" },
        named_group = { "named_group.json" },
        quantifiers = { "quantifiers.json" },
        edges = { "edges.json" },
        escapes = { "escapes.json" },
        escape_and_quantifier = { "escape_and_quantifier.json" },
    )]
    fn happy_path(filename: &str) {
        let path = get_fixture_path(filename);

        let fixture = load_fixture(&path).unwrap();

        let tree = parse_regex(&fixture.pattern).unwrap();

        println!("-- actual tree --\n{}", tree);
        println!("-- expected tree --\n{}", fixture.tree);

        assert_tree_eq(&tree, &fixture.tree);
    }

    fn assert_tree_eq(tree1: &RegexTree, tree2: &RegexTree) {
        assert!(node_eq(
            tree1,
            tree1.get_root_node(),
            tree2,
            tree2.get_root_node()
        ));
    }

    fn node_eq(
        tree1: &RegexTree,
        node1: Option<RegexNode>,
        tree2: &RegexTree,
        node2: Option<RegexNode>,
    ) -> bool {
        if node1.is_none() && node2.is_none() {
            return true;
        }
        if (node1.is_none() && !node2.is_none()) || (!node1.is_none() && node2.is_none()) {
            return false;
        }
        let node1 = node1.unwrap();
        let node2 = node2.unwrap();
        if node1.get_value() != node2.get_value() {
            return false;
        }
        let ids1 = node1.get_children_ids();
        let ids2 = node2.get_children_ids();

        if ids1.len() != ids2.len() {
            return false;
        }

        let iter = zip(ids1, ids2);
        for (id1, id2) in iter {
            let child1 = tree1.get_node_by_id(&id1).unwrap();
            let child2 = tree2.get_node_by_id(&id2).unwrap();
            if !node_eq(tree1, Some(child1), tree2, Some(child2)) {
                return false;
            }
        }
        return true;
    }

    #[parameterized(
        named = { "12(?P<name>bar)", 3, "?P<name>", 11 },
        modifiers = { "12(?ia-x:bar)", 3, "?ia-x:", 9 },
    )]
    fn consume_group_header_happy_path(
        pattern: &str,
        start_idx: usize,
        expected_header: &str,
        expected_idx: usize,
    ) {
        let (header, idx) = consume_group_header(pattern, start_idx).unwrap();
        assert_eq!(header, expected_header);
        assert_eq!(idx, expected_idx);
    }

    #[parameterized(
        one_char = { "f", (None, "f") },
        no_escape = { "foo", (Some("fo"), "o") },
        escaped = { "foo\\n", (Some("foo"), "\\n") },
        escaped_start = { "\\n", (None, "\\n") },
    )]
    fn split_last_char_happy_path(text: &str, expected: (Option<&str>, &str)) {
        let result = split_last_char(text);
        assert_eq!(result, expected);
    }
}
