// SPDX-License-Identifier: MPL-2.0
// SPDX-FileCopyrightText: 2026 Jonathan D.A. Jewell

//! rescript-schema validator generation with topological sorting

use crate::ir::{ApiSpec, TypeDef, Field, RsType};
use super::Config;
use anyhow::Result;
use heck::ToLowerCamelCase;
use std::collections::{HashMap, HashSet, VecDeque};

pub fn generate(spec: &ApiSpec, config: &Config) -> Result<String> {
    let mut output = String::new();

    // Header
    output.push_str("// SPDX-License-Identifier: MPL-2.0\n");
    output.push_str("// Generated by rescript-openapi - DO NOT EDIT\n");
    output.push_str(&format!("// Source: {} v{}\n\n", spec.title, spec.version));

    // Import types
    output.push_str(&format!("open {}Types\n\n", config.module_prefix));

    // Module alias for rescript-schema
    output.push_str("module S = RescriptSchema.S\n\n");

    // Topologically sort types by dependencies
    let sorted_types = topological_sort(&spec.types);

    // Generate schema for each type in dependency order
    for type_def in sorted_types {
        output.push_str(&generate_schema(type_def, config));
        output.push('\n');
    }

    Ok(output)
}

pub fn generate_schema_only(type_def: &TypeDef, config: &Config) -> String {
    let mut output = String::new();
    output.push_str(&generate_schema(type_def, config));
    output
}

/// Extract type dependencies from a TypeDef
pub fn get_dependencies(type_def: &TypeDef) -> HashSet<String> {
    let mut deps = HashSet::new();

    match type_def {
        TypeDef::Record { fields, .. } => {
            for field in fields {
                collect_type_deps(&field.ty, &mut deps);
            }
        }
        TypeDef::Variant { cases, .. } => {
            for case in cases {
                if let Some(ty) = &case.payload {
                    collect_type_deps(ty, &mut deps);
                }
            }
        }
        TypeDef::Alias { target, .. } => {
            collect_type_deps(target, &mut deps);
        }
    }

    deps
}

/// Recursively collect Named type dependencies
fn collect_type_deps(ty: &RsType, deps: &mut HashSet<String>) {
    match ty {
        RsType::Named(name) => {
            deps.insert(name.to_lower_camel_case());
        }
        RsType::Option(inner) | RsType::Array(inner) | RsType::Dict(inner) => {
            collect_type_deps(inner, deps);
        }
        RsType::Tuple(types) => {
            for t in types {
                collect_type_deps(t, deps);
            }
        }
        _ => {}
    }
}

/// Topologically sort types so dependencies come before dependents
pub fn topological_sort(types: &[TypeDef]) -> Vec<&TypeDef> {
    // Build name -> TypeDef map
    let type_map: HashMap<String, &TypeDef> = types
        .iter()
        .map(|t| {
            let name = match t {
                TypeDef::Record { name, .. } => name.to_lower_camel_case(),
                TypeDef::Variant { name, .. } => name.to_lower_camel_case(),
                TypeDef::Alias { name, .. } => name.to_lower_camel_case(),
            };
            (name, t)
        })
        .collect();

    // Build dependency graph (adjacency list: type -> types it depends on)
    let mut deps_map: HashMap<String, HashSet<String>> = HashMap::new();
    let mut all_names: Vec<String> = Vec::new();

    for type_def in types {
        let name = match type_def {
            TypeDef::Record { name, .. } => name.to_lower_camel_case(),
            TypeDef::Variant { name, .. } => name.to_lower_camel_case(),
            TypeDef::Alias { name, .. } => name.to_lower_camel_case(),
        };
        all_names.push(name.clone());

        let deps = get_dependencies(type_def);
        // Only keep deps that are actually in our type set
        let filtered_deps: HashSet<String> = deps
            .into_iter()
            .filter(|d| type_map.contains_key(d))
            .collect();
        deps_map.insert(name, filtered_deps);
    }

    // Kahn's algorithm for topological sort
    // Calculate in-degree (how many types depend on this type)
    let mut in_degree: HashMap<String, usize> = HashMap::new();
    for name in &all_names {
        in_degree.insert(name.clone(), 0);
    }

    // Build reverse graph: for each type, which types depend on it
    for (name, deps) in &deps_map {
        // Each dependency means 'name' has an incoming edge
        // (dep must come before name in the sorted order)
        // Invariant: name was inserted into in_degree during initialization above
        *in_degree.get_mut(name).expect("invariant: all names initialized in in_degree map") += deps.len();
    }

    // Start with types that have no dependencies (sorted for deterministic order)
    let mut zero_degree: Vec<String> = in_degree
        .iter()
        .filter(|(_, &degree)| degree == 0)
        .map(|(name, _)| name.clone())
        .collect();
    zero_degree.sort();
    let mut queue: VecDeque<String> = zero_degree.into_iter().collect();

    let mut sorted: Vec<&TypeDef> = Vec::new();

    while let Some(name) = queue.pop_front() {
        if let Some(&type_def) = type_map.get(&name) {
            sorted.push(type_def);
        }

        // For each type that depends on this one, decrease its in-degree
        // Collect newly ready types and sort them for deterministic order
        let mut newly_ready: Vec<String> = Vec::new();
        for (other_name, other_deps) in &deps_map {
            if other_deps.contains(&name) {
                // Invariant: other_name was inserted into in_degree during initialization
                let degree = in_degree.get_mut(other_name).expect("invariant: all names initialized in in_degree map");
                *degree -= 1;
                if *degree == 0 {
                    newly_ready.push(other_name.clone());
                }
            }
        }
        newly_ready.sort();
        for ready_name in newly_ready {
            queue.push_back(ready_name);
        }
    }

    // If we didn't get all types, there's a cycle - just append remaining
    if sorted.len() < types.len() {
        for type_def in types {
            let name = match type_def {
                TypeDef::Record { name, .. } => name.to_lower_camel_case(),
                TypeDef::Variant { name, .. } => name.to_lower_camel_case(),
                TypeDef::Alias { name, .. } => name.to_lower_camel_case(),
            };
            if !sorted.iter().any(|t| {
                let n = match t {
                    TypeDef::Record { name, .. } => name.to_lower_camel_case(),
                    TypeDef::Variant { name, .. } => name.to_lower_camel_case(),
                    TypeDef::Alias { name, .. } => name.to_lower_camel_case(),
                };
                n == name
            }) {
                sorted.push(type_def);
            }
        }
    }

    sorted
}

/// Sort types into Strongly Connected Components (SCCs) in topological order
/// Returns a list of components, where each component is a list of mutually recursive types.
pub fn topological_sort_scc(types: &[TypeDef]) -> Vec<Vec<&TypeDef>> {
    // Build name -> TypeDef map and index map
    let mut type_map: HashMap<String, &TypeDef> = HashMap::new();
    let mut name_to_index: HashMap<String, usize> = HashMap::new();
    let mut index_to_name: Vec<String> = Vec::new();

    for (i, t) in types.iter().enumerate() {
        let name = match t {
            TypeDef::Record { name, .. } => name.to_lower_camel_case(),
            TypeDef::Variant { name, .. } => name.to_lower_camel_case(),
            TypeDef::Alias { name, .. } => name.to_lower_camel_case(),
        };
        type_map.insert(name.clone(), t);
        name_to_index.insert(name.clone(), i);
        index_to_name.push(name);
    }

    // Build adjacency list
    let mut adj: Vec<Vec<usize>> = vec![Vec::new(); types.len()];
    for (i, type_def) in types.iter().enumerate() {
        let deps = get_dependencies(type_def);
        let mut sorted_deps: Vec<String> = deps.into_iter().collect();
        sorted_deps.sort();
        
        for dep_name in sorted_deps {
            if let Some(&dep_idx) = name_to_index.get(&dep_name) {
                // Dependency: i depends on dep_idx
                // For Tarjan's on dependency graph, edge i -> dep_idx
                adj[i].push(dep_idx);
            }
        }
    }

    // Tarjan's Algorithm
    let n = types.len();
    let mut visited = vec![false; n];
    let mut stack = Vec::new();
    let mut on_stack = vec![false; n];
    let mut ids = vec![-1; n];
    let mut low = vec![-1; n];
    let mut id_counter = 0;
    let mut sccs: Vec<Vec<usize>> = Vec::new();

    for i in 0..n {
        if !visited[i] {
            tarjan_dfs(
                i,
                &adj,
                &mut visited,
                &mut stack,
                &mut on_stack,
                &mut ids,
                &mut low,
                &mut id_counter,
                &mut sccs,
            );
        }
    }

    // Tarjan's returns SCCs in reverse topological order (leaves first)
    // We want dependencies first, so we use the order as is (reverse topo).
    // Wait, Tarjan returns reverse topological order of the condensation graph?
    // "The SCCs are found in reverse topological order."
    // If A depends on B, and they are in different SCCs, B's SCC will be found first.
    // This is exactly what we want: print dependencies (B) before dependents (A).

    let mut result = Vec::new();
    for scc_indices in sccs {
        let mut scc_types = Vec::new();
        for &idx in &scc_indices {
            scc_types.push(&types[idx]);
        }
        result.push(scc_types);
    }

    result
}

#[allow(clippy::too_many_arguments)]
fn tarjan_dfs(
    at: usize,
    adj: &Vec<Vec<usize>>,
    visited: &mut Vec<bool>,
    stack: &mut Vec<usize>,
    on_stack: &mut Vec<bool>,
    ids: &mut Vec<i32>,
    low: &mut Vec<i32>,
    id_counter: &mut i32,
    sccs: &mut Vec<Vec<usize>>,
) {
    visited[at] = true;
    stack.push(at);
    on_stack[at] = true;
    ids[at] = *id_counter;
    low[at] = *id_counter;
    *id_counter += 1;

    for &to in &adj[at] {
        if !visited[to] {
            tarjan_dfs(
                to, adj, visited, stack, on_stack, ids, low, id_counter, sccs,
            );
            low[at] = std::cmp::min(low[at], low[to]);
        } else if on_stack[to] {
            low[at] = std::cmp::min(low[at], ids[to]);
        }
    }

    if ids[at] == low[at] {
        let mut component = Vec::new();
        loop {
            // Invariant: Tarjan SCC algorithm guarantees stack is non-empty when ids[at] == low[at]
            let node = stack.pop().expect("invariant: stack non-empty in Tarjan SCC root");
            on_stack[node] = false;
            component.push(node);
            if node == at {
                break;
            }
        }
        sccs.push(component);
    }
}

fn generate_schema(type_def: &TypeDef, config: &Config) -> String {
    let mut output = String::new();

    match type_def {
        TypeDef::Record { name, doc, fields } => {
            let schema_name = format!("{}Schema", name.to_lower_camel_case());

            if let Some(doc) = doc {
                output.push_str(&format!("/** Schema for {} */\n", doc));
            }

            let type_name = name.to_lower_camel_case();
            output.push_str(&format!("let {}: S.t<{}> = S.object(s => ({{\n", schema_name, type_name));

            for field in fields {
                output.push_str(&generate_field_schema(field));
            }

            output.push_str(&format!("}}: {}))\n", type_name));
        }

        TypeDef::Variant { name, doc, cases } => {
            let schema_name = format!("{}Schema", name.to_lower_camel_case());
            let type_name = name.to_lower_camel_case();

            if let Some(doc) = doc {
                output.push_str(&format!("/** Schema for {} */\n", doc));
            }

            // String enum variant
            if cases.iter().all(|c| c.payload.is_none()) {
                if config.variant_mode == super::VariantMode::Standard {
                    // Standard variant - use S.enum
                    output.push_str(&format!("let {}: S.t<{}> = S.enum([\n", schema_name, type_name));
                    for case in cases {
                        output.push_str(&format!("  {},\n", case.name));
                    }
                    output.push_str("])\n");
                } else {
                    // Polymorphic variant - use S.union with literals
                    output.push_str(&format!("let {}: S.t<{}> = S.union([\n", schema_name, type_name));

                    for case in cases {
                        output.push_str(&format!(
                            "  S.literal(#{}),\n",
                            case.name
                        ));
                    }

                    output.push_str("])\n");
                }
            } else {
                // oneOf/anyOf variant - wrap each referenced type's schema
                output.push_str(&format!("let {}: S.t<{}> = S.union([\n", schema_name, type_name));

                for case in cases {
                    match &case.payload {
                        Some(ty) => {
                            // Wrap the inner schema to transform to variant constructor
                            output.push_str(&format!(
                                "  {}->S.transform(s => {{\n    parser: v => {}(v),\n    serializer: v => switch v {{ | {}(x) => x | _ => S.fail(\"Expected {}\") }}\n  }}),\n",
                                ty.to_schema(),
                                case.name,
                                case.name,
                                case.name
                            ));
                        }
                        None => {
                            // No payload - literal variant
                            output.push_str(&format!(
                                "  S.literal(\"{}\")->S.transform(s => {{\n    parser: _ => {},\n    serializer: _ => \"{}\"\n  }}),\n",
                                case.original_name,
                                case.name,
                                case.original_name
                            ));
                        }
                    }
                }

                output.push_str("])\n");
            }
        }

        TypeDef::Alias { name, doc, target } => {
            let schema_name = format!("{}Schema", name.to_lower_camel_case());

            if let Some(doc) = doc {
                output.push_str(&format!("/** Schema for {} */\n", doc));
            }

            output.push_str(&format!("let {} = {}\n", schema_name, target.to_schema()));
        }
    }

    output
}

fn generate_field_schema(field: &Field) -> String {
    let method = if field.optional { "fieldOr" } else { "field" };
    let default = if field.optional {
        ", None"
    } else {
        ""
    };

    let schema = field.ty.to_schema();

    if field.name != field.original_name {
        format!(
            "  {}: s.{}(\"{}\", {}{}),\n",
            field.name,
            method,
            field.original_name,
            schema,
            default
        )
    } else {
        format!(
            "  {}: s.{}(\"{}\", {}{}),\n",
            field.name,
            method,
            field.name,
            schema,
            default
        )
    }
}
