//! 模块依赖图构建与分析
//!
//! 解析每个源文件的 import/export，构建 DAG，支持拓扑排序和闭包计算。

use std::collections::{HashMap, HashSet, VecDeque};
use std::path::{Path, PathBuf};

use crate::project::Project;
use crate::swc_transform::parse;

/// 模块节点
#[derive(Debug, Clone)]
pub struct ModuleNode {
    /// 文件路径
    pub path: PathBuf,
    /// 模块名
    pub module_name: String,
    /// 导出的函数名
    pub exports: HashSet<String>,
    /// 导入的模块（模块路径 -> 导入的符号列表）
    pub imports: HashMap<PathBuf, Vec<String>>,
    /// 依赖的模块路径（项目内模块）
    pub deps: Vec<PathBuf>,
    /// 被哪些模块依赖
    pub reverse_deps: Vec<PathBuf>,
    /// 编译层级（0 = 叶子模块，无项目内依赖）
    pub level: usize,
    /// 是否为入口
    pub is_entry: bool,
    /// 是否为 shim 依赖（不需要编译）
    pub is_shim: bool,
    /// 模块唯一数字 ID（基于编译序分配）
    pub module_id: u32,
}

/// 依赖图
#[derive(Debug)]
pub struct DepGraph {
    /// 所有模块节点
    pub nodes: HashMap<PathBuf, ModuleNode>,
    /// 入口 -> 其依赖闭包（包含自身）
    pub entry_closures: HashMap<PathBuf, Vec<PathBuf>>,
    /// 按层级排序的编译顺序
    pub compile_order: Vec<PathBuf>,
    /// 模块路径 → 模块数字 ID
    pub module_id_map: HashMap<PathBuf, u32>,
    /// 模块路径 → {原始导出名 → 全局唯一符号名（mod_{id}_{name}）}
    pub export_map: HashMap<PathBuf, HashMap<String, String>>,
}

impl DepGraph {
    /// 从项目构建依赖图
    pub fn from_project(project: &mut Project) -> anyhow::Result<Self> {
        let mut nodes = HashMap::new();

        // 第一步：收集所有文件路径（避免借用冲突）
        let paths: Vec<PathBuf> = project.files.keys().cloned().collect();

        // 第二步：解析所有文件的 import/export
        for path in &paths {
            let content = project.load_content(path)?;
            let (exports, imports) = Self::parse_module_interface(&content)?;

            // 解析导入的模块路径
            let mut deps = Vec::new();
            let mut import_map: HashMap<PathBuf, Vec<String>> = HashMap::new();

            for (specifier, symbols) in &imports {
                if let Some(dep_path) = project.resolve_import(path, specifier) {
                    // 检查是否为 shim 路径
                    if Project::is_shim_path(&dep_path) {
                        // shim 依赖：记录但不加入 deps（不需要编译）
                        import_map.insert(dep_path, symbols.clone());
                    } else {
                        deps.push(dep_path.clone());
                        import_map.insert(dep_path, symbols.clone());
                    }
                }
                // 内置模块（如 "fs"）不加入 deps
            }

            let module_name = project.files.get(path)
                .map(|f| f.module_name.clone())
                .unwrap_or_default();
            let is_entry = project.files.get(path)
                .map(|f| f.is_entry)
                .unwrap_or(false);

            nodes.insert(path.clone(), ModuleNode {
                path: path.clone(),
                module_name,
                exports,
                imports: import_map,
                deps,
                reverse_deps: Vec::new(),
                level: 0,
                is_entry,
                is_shim: false,
                module_id: 0,
            });
        }

        // 第二步：构建反向依赖
        let paths: Vec<PathBuf> = nodes.keys().cloned().collect();
        for path in &paths {
            let deps = nodes.get(path).unwrap().deps.clone();
            for dep in deps {
                if let Some(node) = nodes.get_mut(&dep) {
                    node.reverse_deps.push(path.clone());
                }
            }
        }

        // 第三步：计算编译层级（拓扑排序）
        let compile_order = Self::topological_sort(&nodes)?;

        // 计算每个节点的层级
        for path in &compile_order {
            let level = if let Some(node) = nodes.get(path) {
                if node.deps.is_empty() {
                    0
                } else {
                    node.deps.iter()
                        .filter_map(|d| nodes.get(d).map(|n| n.level))
                        .max()
                        .unwrap_or(0) + 1
                }
            } else {
                0
            };
            if let Some(node) = nodes.get_mut(path) {
                node.level = level;
            }
        }

        // 第四步：分配模块 ID（基于编译序，从 1 开始，保证唯一）
        let mut module_id_map: HashMap<PathBuf, u32> = HashMap::new();
        let mut mod_counter = 1u32;
        for path in &compile_order {
            module_id_map.insert(path.clone(), mod_counter);
            if let Some(node) = nodes.get_mut(path) {
                node.module_id = mod_counter;
            }
            mod_counter += 1;
        }

        // 第五步：构建导出映射表 {原始名 → mod_{id}_原始名}
        let mut export_map: HashMap<PathBuf, HashMap<String, String>> = HashMap::new();
        for (path, node) in &nodes {
            let id = node.module_id;
            let mut map = HashMap::new();
            for exported in &node.exports {
                map.insert(exported.clone(), format!("mod_{}_{}", id, exported));
            }
            export_map.insert(path.clone(), map);
        }

        // 第六步：计算每个入口的依赖闭包
        let mut entry_closures = HashMap::new();
        for entry_path in &project.entries {
            let closure = Self::compute_closure(entry_path, &nodes);
            entry_closures.insert(entry_path.clone(), closure);
        }

        Ok(DepGraph {
            nodes,
            entry_closures,
            compile_order,
            module_id_map,
            export_map,
        })
    }

    /// 解析模块接口（导出和导入）
    /// 使用 SWC 全量解析，从 HIR 中的 Export/ImportBinding 节点提取信息
    ///
    /// 返回：(导出的函数名列表, 导入的模块 -> 符号列表)
    fn parse_module_interface(content: &str) -> anyhow::Result<(HashSet<String>, HashMap<String, Vec<String>>)> {
        let mut exports = HashSet::new();
        let mut imports: HashMap<String, Vec<String>> = HashMap::new();

        // 使用 SWC 解析
        let hir = parse(content)?;

        for expr in &hir {
            match expr {
                // 命名导出：export { a, b } / export function foo() / export const x = 1
                crate::codegen::HirExpr::Export { exported, module, .. } => {
                    if module.is_empty() {
                        // 当前模块的导出
                        exports.insert(exported.clone());
                    } else if exported == "*" {
                        // export * from "./mod" → 标记为星号导出（后续在依赖图中展开）
                        exports.insert(format!("__export_star__{}", module));
                    } else {
                        // export { x } from "./mod" → re-export
                        exports.insert(exported.clone());
                    }
                }
                // 导入绑定
                crate::codegen::HirExpr::ImportBinding { local: _, module, imported } => {
                    let entry = imports.entry(module.clone()).or_insert_with(Vec::new);
                    if imported != "*" && imported != "default" {
                        entry.push(imported.clone());
                    }
                }
                // CJS require 通过 Var 包装的 ImportBinding
                // const x = require("mod") -> Var { init: ImportBinding { ... } }
                // 也需要识别其中的 ImportBinding
                crate::codegen::HirExpr::Var { name: _, init, is_mut: _ } => {
                    if let Some(init_expr) = init {
                        if let crate::codegen::HirExpr::ImportBinding { local: _, module, imported } = init_expr.as_ref() {
                            let entry = imports.entry(module.clone()).or_insert_with(Vec::new);
                            if imported != "*" && imported != "default" {
                                entry.push(imported.clone());
                            }
                        }
                    }
                }
                _ => {}
            }
        }

        Ok((exports, imports))
    }

    /// 拓扑排序（Kahn 算法）
    fn topological_sort(nodes: &HashMap<PathBuf, ModuleNode>) -> anyhow::Result<Vec<PathBuf>> {
        let mut in_degree: HashMap<PathBuf, usize> = HashMap::new();
        let mut adj: HashMap<PathBuf, Vec<PathBuf>> = HashMap::new();

        // 初始化
        for (path, node) in nodes {
            in_degree.entry(path.clone()).or_insert(0);
            for dep in &node.deps {
                adj.entry(dep.clone()).or_insert_with(Vec::new).push(path.clone());
                *in_degree.entry(path.clone()).or_insert(0) += 1;
            }
        }

        // Kahn 算法
        let mut queue: VecDeque<PathBuf> = VecDeque::new();
        for (path, degree) in &in_degree {
            if *degree == 0 {
                queue.push_back(path.clone());
            }
        }

        let mut result = Vec::new();
        while let Some(path) = queue.pop_front() {
            result.push(path.clone());

            if let Some(neighbors) = adj.get(&path) {
                for neighbor in neighbors {
                    if let Some(degree) = in_degree.get_mut(neighbor) {
                        *degree -= 1;
                        if *degree == 0 {
                            queue.push_back(neighbor.clone());
                        }
                    }
                }
            }
        }

        if result.len() != nodes.len() {
            anyhow::bail!("依赖图中存在循环依赖");
        }

        Ok(result)
    }

    /// 计算某个模块的依赖闭包（包含自身）
    fn compute_closure(start: &Path, nodes: &HashMap<PathBuf, ModuleNode>) -> Vec<PathBuf> {
        let mut visited = HashSet::new();
        let mut result = Vec::new();
        let mut stack = vec![start.to_path_buf()];

        while let Some(path) = stack.pop() {
            if visited.insert(path.clone()) {
                result.push(path.clone());
                if let Some(node) = nodes.get(&path) {
                    for dep in &node.deps {
                        if !visited.contains(dep) {
                            stack.push(dep.clone());
                        }
                    }
                }
            }
        }

        result
    }

    /// 获取某个入口需要链接的所有模块（按编译顺序）
    pub fn get_entry_modules(&self, entry: &Path) -> Vec<PathBuf> {
        self.entry_closures
            .get(entry)
            .cloned()
            .unwrap_or_default()
    }

    /// 获取全局编译顺序（所有模块，按层级排序）
    pub fn get_compile_order(&self) -> &[PathBuf] {
        &self.compile_order
    }

    /// 获取模块的导出符号
    pub fn get_module_exports(&self, path: &Path) -> Option<&HashSet<String>> {
        self.nodes.get(path).map(|n| &n.exports)
    }

    /// 获取模块的导入信息
    pub fn get_module_imports(&self, path: &Path) -> Option<&HashMap<PathBuf, Vec<String>>> {
        self.nodes.get(path).map(|n| &n.imports)
    }
}

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

    fn make_node(path: PathBuf, deps: Vec<PathBuf>, is_entry: bool) -> ModuleNode {
        ModuleNode {
            path,
            module_name: String::new(),
            exports: HashSet::new(),
            imports: HashMap::new(),
            deps,
            reverse_deps: Vec::new(),
            level: 0,
            is_entry,
            is_shim: false,
            module_id: 0,
        }
    }

    // === 拓扑排序测试 ===

    #[test]
    fn test_topological_sort_simple_chain() {
        // A → B → C（A 依赖 B，B 依赖 C）
        let a = PathBuf::from("/src/a.ts");
        let b = PathBuf::from("/src/b.ts");
        let c = PathBuf::from("/src/c.ts");

        let mut nodes = HashMap::new();
        nodes.insert(a.clone(), make_node(a.clone(), vec![b.clone()], true));
        nodes.insert(b.clone(), make_node(b.clone(), vec![c.clone()], false));
        nodes.insert(c.clone(), make_node(c.clone(), vec![], false));

        let order = DepGraph::topological_sort(&nodes).unwrap();
        let pos_c = order.iter().position(|p| p == &c).unwrap();
        let pos_b = order.iter().position(|p| p == &b).unwrap();
        let pos_a = order.iter().position(|p| p == &a).unwrap();
        assert!(pos_c < pos_b, "C 应在 B 之前编译");
        assert!(pos_b < pos_a, "B 应在 A 之前编译");
    }

    #[test]
    fn test_topological_sort_diamond() {
        let a = PathBuf::from("/src/a.ts");
        let b = PathBuf::from("/src/b.ts");
        let c = PathBuf::from("/src/c.ts");
        let d = PathBuf::from("/src/d.ts");

        let mut nodes = HashMap::new();
        nodes.insert(a.clone(), make_node(a.clone(), vec![b.clone(), c.clone()], true));
        nodes.insert(b.clone(), make_node(b.clone(), vec![d.clone()], false));
        nodes.insert(c.clone(), make_node(c.clone(), vec![d.clone()], false));
        nodes.insert(d.clone(), make_node(d.clone(), vec![], false));

        let order = DepGraph::topological_sort(&nodes).unwrap();
        let pos_d = order.iter().position(|p| p == &d).unwrap();
        let pos_b = order.iter().position(|p| p == &b).unwrap();
        let pos_c = order.iter().position(|p| p == &c).unwrap();
        let pos_a = order.iter().position(|p| p == &a).unwrap();
        assert!(pos_d < pos_b, "D 应在 B 之前");
        assert!(pos_d < pos_c, "D 应在 C 之前");
        assert!(pos_b < pos_a, "B 应在 A 之前");
        assert!(pos_c < pos_a, "C 应在 A 之前");
        assert_eq!(order.len(), 4);
    }

    #[test]
    fn test_topological_sort_cycle_detection() {
        let a = PathBuf::from("/src/a.ts");
        let b = PathBuf::from("/src/b.ts");

        let mut nodes = HashMap::new();
        nodes.insert(a.clone(), make_node(a.clone(), vec![b.clone()], true));
        nodes.insert(b.clone(), make_node(b.clone(), vec![a.clone()], false));

        let result = DepGraph::topological_sort(&nodes);
        assert!(result.is_err(), "循环依赖应返回错误");
    }

    #[test]
    fn test_topological_sort_single_node() {
        let a = PathBuf::from("/src/a.ts");
        let mut nodes = HashMap::new();
        nodes.insert(a.clone(), make_node(a.clone(), vec![], true));

        let order = DepGraph::topological_sort(&nodes).unwrap();
        assert_eq!(order.len(), 1);
        assert_eq!(order[0], a);
    }

    #[test]
    fn test_topological_sort_independent_nodes() {
        let a = PathBuf::from("/src/a.ts");
        let b = PathBuf::from("/src/b.ts");

        let mut nodes = HashMap::new();
        nodes.insert(a.clone(), make_node(a.clone(), vec![], true));
        nodes.insert(b.clone(), make_node(b.clone(), vec![], false));

        let order = DepGraph::topological_sort(&nodes).unwrap();
        assert_eq!(order.len(), 2);
    }

    // === 闭包计算测试 ===

    #[test]
    fn test_compute_closure_simple() {
        let a = PathBuf::from("/src/a.ts");
        let b = PathBuf::from("/src/b.ts");
        let c = PathBuf::from("/src/c.ts");

        let mut nodes = HashMap::new();
        nodes.insert(a.clone(), make_node(a.clone(), vec![b.clone()], true));
        nodes.insert(b.clone(), make_node(b.clone(), vec![c.clone()], false));
        nodes.insert(c.clone(), make_node(c.clone(), vec![], false));

        let closure = DepGraph::compute_closure(&a, &nodes);
        assert_eq!(closure.len(), 3);
        assert!(closure.contains(&a));
        assert!(closure.contains(&b));
        assert!(closure.contains(&c));
    }

    #[test]
    fn test_compute_closure_leaf() {
        let c = PathBuf::from("/src/c.ts");
        let mut nodes = HashMap::new();
        nodes.insert(c.clone(), make_node(c.clone(), vec![], false));

        let closure = DepGraph::compute_closure(&c, &nodes);
        assert_eq!(closure.len(), 1);
        assert!(closure.contains(&c));
    }

    #[test]
    fn test_compute_closure_diamond() {
        let a = PathBuf::from("/src/a.ts");
        let b = PathBuf::from("/src/b.ts");
        let c = PathBuf::from("/src/c.ts");
        let d = PathBuf::from("/src/d.ts");

        let mut nodes = HashMap::new();
        nodes.insert(a.clone(), make_node(a.clone(), vec![b.clone(), c.clone()], true));
        nodes.insert(b.clone(), make_node(b.clone(), vec![d.clone()], false));
        nodes.insert(c.clone(), make_node(c.clone(), vec![d.clone()], false));
        nodes.insert(d.clone(), make_node(d.clone(), vec![], false));

        let closure = DepGraph::compute_closure(&a, &nodes);
        assert_eq!(closure.len(), 4);
        assert!(closure.contains(&a));
        assert!(closure.contains(&b));
        assert!(closure.contains(&c));
        assert!(closure.contains(&d));
    }

    // === 模块接口解析测试 ===

    #[test]
    fn test_parse_module_interface_exports() {
        let content = "export function foo() { return 1; }\nexport function bar() { return 2; }";
        let (exports, imports) = DepGraph::parse_module_interface(content).unwrap();
        assert!(exports.contains("foo"));
        assert!(exports.contains("bar"));
        assert!(imports.is_empty());
    }

    #[test]
    fn test_parse_module_interface_imports() {
        let content = "import { readFile, writeFile } from 'fs';";
        let (_exports, imports) = DepGraph::parse_module_interface(content).unwrap();
        let fs_imports = imports.get("fs").unwrap();
        assert!(fs_imports.contains(&"readFile".to_string()));
        assert!(fs_imports.contains(&"writeFile".to_string()));
    }

    #[test]
    fn test_parse_module_interface_cjs_require() {
        let content = "const lodash = require(\"lodash\");";
        let (exports, imports) = DepGraph::parse_module_interface(content).unwrap();
        assert!(exports.is_empty());
        assert!(imports.is_empty());
    }

    #[test]
    fn test_parse_module_interface_mixed() {
        let content = r#"
            import { readFile } from 'fs';
            import { debounce } from 'lodash';
            export function main() { return 1; }
        "#;
        let (exports, imports) = DepGraph::parse_module_interface(content).unwrap();
        assert!(exports.contains("main"));
        assert!(imports.contains_key("fs"));
        assert!(imports.contains_key("lodash"));
    }
}
