knott 0.1.4

use crate::aur::{AurClient, AurPackage};
use crate::cli::{Options, SearchBy};
use crate::dep::{parse_dependency, Dependency};
use crate::localdb::LocalDb;
use crate::pacman::Toolchain;
use anyhow::{bail, Result};
use std::collections::{BTreeSet, HashMap, HashSet, VecDeque};

pub(crate) const MAX_RESOLVE_NODES: usize = 4096;

#[derive(Debug, Clone, Default)]
pub struct Plan {
    pub aur: Vec<AurPackage>,
    pub repo_deps: Vec<String>,
    pub unresolved: Vec<String>,
}

#[derive(Debug, Clone)]
struct Request {
    raw: String,
    direct: bool,
}

#[derive(Debug, Clone)]
struct ParsedRequest {
    request: Request,
    dep: Dependency,
}

pub async fn resolve(
    options: &Options,
    tools: &Toolchain,
    aur: &AurClient,
    local: &LocalDb,
    targets: &[String],
) -> Result<Plan> {
    let mut queue = targets
        .iter()
        .cloned()
        .map(|raw| Request { raw, direct: true })
        .collect::<VecDeque<_>>();

    let mut nodes: HashMap<String, AurPackage> = HashMap::new();
    let mut repo_cache: HashMap<String, bool> = HashMap::new();
    let mut repo_deps = BTreeSet::new();
    let mut unresolved = Vec::new();

    while !queue.is_empty() {
        let mut batch = Vec::new();
        let mut info_names = Vec::new();
        let mut seen_info = HashSet::new();

        while let Some(request) = queue.pop_front() {
            let dep = parse_dependency(&request.raw);

            if !request.direct && local.satisfies(&request.raw) {
                continue;
            }

            if nodes.contains_key(&dep.name) {
                continue;
            }

            if !request.direct && options.mode.repo() {
                let repo_has = if let Some(repo_has) = repo_cache.get(&dep.name) {
                    *repo_has
                } else {
                    let value = tools.repo_has_package(&dep.name).await;
                    repo_cache.insert(dep.name.clone(), value);
                    value
                };

                if repo_has {
                    repo_deps.insert(dep.name.clone());
                    continue;
                }
            }

            if seen_info.insert(dep.name.clone()) {
                info_names.push(dep.name.clone());
            }
            batch.push(ParsedRequest { request, dep });
        }

        if batch.is_empty() {
            continue;
        }

        if nodes.len() + batch.len() > MAX_RESOLVE_NODES {
            bail!("AUR dependency graph exceeded {MAX_RESOLVE_NODES} packages");
        }

        let packages = aur.info_map(&info_names).await?;

        for parsed in batch {
            if nodes.contains_key(&parsed.dep.name) {
                continue;
            }

            let package = match packages.get(&parsed.dep.name).cloned() {
                Some(pkg) => Some(pkg),
                None if !parsed.request.direct => choose_provider(aur, &parsed.dep.name).await?,
                None => None,
            };

            let Some(package) = package else {
                if parsed.request.direct {
                    bail!("AUR package '{}' was not found", parsed.dep.name);
                }
                unresolved.push(parsed.request.raw);
                continue;
            };

            if nodes.contains_key(&package.name) {
                continue;
            }

            for child in package_dependencies(options, &package) {
                if nodes.len() + queue.len() + 1 > MAX_RESOLVE_NODES {
                    bail!("AUR dependency graph exceeded {MAX_RESOLVE_NODES} packages");
                }
                queue.push_back(Request {
                    raw: child.clone(),
                    direct: false,
                });
            }

            nodes.insert(package.name.clone(), package);
        }
    }

    let ordered = topo_sort(&nodes, options)?;

    Ok(Plan {
        aur: ordered,
        repo_deps: repo_deps.into_iter().collect(),
        unresolved,
    })
}

async fn choose_provider(aur: &AurClient, dep_name: &str) -> Result<Option<AurPackage>> {
    let mut providers = aur.search_by_term(dep_name, SearchBy::Provides).await?;
    providers.retain(|pkg| {
        pkg.provides
            .iter()
            .any(|provide| parse_dependency(provide).name == dep_name)
    });
    providers.sort_by(|left, right| {
        right
            .num_votes
            .cmp(&left.num_votes)
            .then_with(|| {
                right
                    .popularity
                    .partial_cmp(&left.popularity)
                    .unwrap_or(std::cmp::Ordering::Equal)
            })
            .then_with(|| left.name.cmp(&right.name))
    });
    Ok(providers.into_iter().next())
}

fn package_dependencies<'a>(
    options: &'a Options,
    pkg: &'a AurPackage,
) -> impl Iterator<Item = &'a String> {
    pkg.depends.iter().chain(pkg.make_depends.iter()).chain(
        (!options.no_check)
            .then_some(pkg.check_depends.iter())
            .into_iter()
            .flatten(),
    )
}

fn topo_sort(nodes: &HashMap<String, AurPackage>, options: &Options) -> Result<Vec<AurPackage>> {
    let mut temporary = HashSet::new();
    let mut permanent = HashSet::new();
    let mut ordered = Vec::with_capacity(nodes.len());

    let mut names = nodes.keys().cloned().collect::<Vec<_>>();
    names.sort();

    for name in names {
        visit(
            &name,
            nodes,
            options,
            &mut temporary,
            &mut permanent,
            &mut ordered,
        )?;
    }

    Ok(ordered)
}

fn visit(
    name: &str,
    nodes: &HashMap<String, AurPackage>,
    options: &Options,
    temporary: &mut HashSet<String>,
    permanent: &mut HashSet<String>,
    ordered: &mut Vec<AurPackage>,
) -> Result<()> {
    if permanent.contains(name) {
        return Ok(());
    }
    if !temporary.insert(name.to_string()) {
        bail!("dependency cycle involving '{name}'");
    }

    let Some(pkg) = nodes.get(name) else {
        return Ok(());
    };

    for dep in package_dependencies(options, pkg) {
        if let Some(dep_name) = dep_to_node(nodes, dep) {
            visit(&dep_name, nodes, options, temporary, permanent, ordered)?;
        }
    }

    temporary.remove(name);
    permanent.insert(name.to_string());
    ordered.push(pkg.clone());
    Ok(())
}

fn dep_to_node(nodes: &HashMap<String, AurPackage>, raw_dep: &str) -> Option<String> {
    let dep = parse_dependency(raw_dep);
    if nodes.contains_key(&dep.name) {
        return Some(dep.name);
    }

    nodes.iter().find_map(|(name, pkg)| {
        pkg.provides
            .iter()
            .any(|provide| parse_dependency(provide).name == dep.name)
            .then(|| name.clone())
    })
}