knott 0.0.1

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

#[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,
}

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 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;
            }
        }

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

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

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

        for child in package_dependencies(options, &package) {
            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())
    })
}