use crate::aur::{AurClient, AurPackage};
use crate::cli::{Options, SearchBy};
use crate::dep::{dependency_satisfied, 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_satisfy_dependency(&nodes, &dep) {
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_satisfy_dependency(&nodes, &parsed.dep) {
continue;
}
let direct_plain_target =
parsed.request.direct && parsed.request.raw == parsed.dep.name;
let exact = match packages.get(&parsed.dep.name).cloned() {
Some(pkg) if options.prefer_bin => {
Some(preferred_bin_package(aur, &parsed.dep, direct_plain_target, pkg).await?)
}
Some(pkg) => Some(pkg),
None => None,
};
let package = if let Some(pkg) = exact {
if direct_plain_target || package_satisfies_dependency(&pkg, &parsed.dep) {
Some(pkg)
} else if parsed.request.direct {
bail!(
"AUR package '{}' version {} does not satisfy '{}'",
pkg.name,
pkg.version,
parsed.request.raw
);
} else {
choose_provider(options, aur, &parsed.dep).await?
}
} else if !parsed.request.direct {
choose_provider(options, aur, &parsed.dep).await?
} else {
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 preferred_bin_package(
aur: &AurClient,
dep: &Dependency,
direct: bool,
fallback: AurPackage,
) -> Result<AurPackage> {
let dep_name = &dep.name;
let Some(candidate) = bin_candidate_name(dep_name) else {
return Ok(fallback);
};
let packages = aur.info_map(std::slice::from_ref(&candidate)).await?;
let Some(package) = packages.get(&candidate).cloned() else {
return Ok(fallback);
};
if direct || package_satisfies_dependency(&package, dep) {
Ok(package)
} else {
Ok(fallback)
}
}
async fn choose_provider(
options: &Options,
aur: &AurClient,
dep: &Dependency,
) -> Result<Option<AurPackage>> {
let mut providers = aur.search_by_term(&dep.name, SearchBy::Provides).await?;
providers.retain(|pkg| package_satisfies_dependency(pkg, dep));
providers.sort_by(|left, right| {
if options.prefer_bin {
let ordering = right
.name
.ends_with("-bin")
.cmp(&left.name.ends_with("-bin"));
if ordering != std::cmp::Ordering::Equal {
return ordering;
}
}
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 nodes_satisfy_dependency(nodes: &HashMap<String, AurPackage>, dep: &Dependency) -> bool {
nodes
.values()
.any(|pkg| package_satisfies_dependency(pkg, dep))
}
fn package_satisfies_dependency(pkg: &AurPackage, dep: &Dependency) -> bool {
if pkg.name == dep.name && dependency_satisfied(&pkg.version, dep) {
return true;
}
package_provides_dependency(pkg, dep)
}
fn package_provides_dependency(pkg: &AurPackage, dep: &Dependency) -> bool {
pkg.provides
.iter()
.any(|provide| provide_satisfies_dependency(pkg, provide, dep))
}
fn provide_satisfies_dependency(pkg: &AurPackage, raw_provide: &str, dep: &Dependency) -> bool {
let provide = parse_dependency(raw_provide);
if provide.name != dep.name {
return false;
}
if dep.op.is_none() {
return true;
}
let version = provide.version.as_deref().unwrap_or(&pkg.version);
dependency_satisfied(version, dep)
}
fn bin_candidate_name(name: &str) -> Option<String> {
if name.ends_with("-bin") || name.bytes().any(|byte| matches!(byte, b'<' | b'>' | b'=')) {
return None;
}
Some(format!("{name}-bin"))
}
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
.get(&dep.name)
.is_some_and(|pkg| package_satisfies_dependency(pkg, &dep))
{
return Some(dep.name);
}
nodes
.iter()
.find_map(|(name, pkg)| package_provides_dependency(pkg, &dep).then(|| name.clone()))
}
#[cfg(test)]
mod tests {
use super::*;
fn package(name: &str, version: &str, provides: &[&str]) -> AurPackage {
AurPackage {
name: name.to_string(),
version: version.to_string(),
provides: provides.iter().map(|value| (*value).to_string()).collect(),
..AurPackage::default()
}
}
#[test]
fn package_satisfaction_checks_exact_package_versions() {
let pkg = package("foo", "1.5-1", &[]);
assert!(package_satisfies_dependency(
&pkg,
&parse_dependency("foo>=1.0")
));
assert!(!package_satisfies_dependency(
&pkg,
&parse_dependency("foo>=2.0")
));
}
#[test]
fn package_satisfaction_checks_provided_versions() {
let pkg = package("provider", "9.0-1", &["virtual=1.5"]);
assert!(package_satisfies_dependency(
&pkg,
&parse_dependency("virtual>=1.0")
));
assert!(!package_satisfies_dependency(
&pkg,
&parse_dependency("virtual>=2.0")
));
}
#[test]
fn unversioned_provides_use_package_version_for_versioned_deps() {
let pkg = package("provider", "2.1-1", &["virtual"]);
assert!(package_satisfies_dependency(
&pkg,
&parse_dependency("virtual>=2.0")
));
}
#[test]
fn dep_to_node_rejects_too_old_provider() {
let mut nodes = HashMap::new();
nodes.insert(
"old-provider".to_string(),
package("old-provider", "9.0-1", &["virtual=1.0"]),
);
assert_eq!(dep_to_node(&nodes, "virtual>=2.0"), None);
nodes.clear();
nodes.insert(
"new-provider".to_string(),
package("new-provider", "1.0-1", &["virtual=2.0"]),
);
assert_eq!(
dep_to_node(&nodes, "virtual>=2.0"),
Some("new-provider".into())
);
}
}