server/lib/src/pull_intake/closures.rs
//! **The npm, cargo and Python closures** (lane HOL-DEPSET-APPROVE): what a pull of one
//! version brings into the intake chain with it, read from the registries' own metadata,
//! so the approvers judge the closure as ONE set ([`super::depset`]). Maven's is
//! [`super::pom`].
//!
//! * **npm**: each version's `dependencies`, `optionalDependencies` and the required
//! `peerDependencies` from its packument, each range resolved to the version npm takes
//! (`latest` when it satisfies, else the highest that does);
//! * **cargo**: each version's normal and build dependencies from the sparse index (not
//! dev, not optional; every target, as `cargo fetch` takes them), each requirement
//! resolved to the highest unyanked version;
//! * **Python**: each wheel's `Requires-Dist` (PEP 658 metadata, else the wheel's own
//! `METADATA`), markers judged for CPython 3.12 on x86_64 Linux and no extras, each
//! specifier resolved to the newest final release that satisfies it.
//!
//! A dependency the registry does not publish, or a range nothing satisfies, is named
//! unresolved and holds the set (fail closed). An optional npm dependency that cannot be
//! resolved is left out, as npm leaves it out.
use std::cmp::Ordering;
use std::collections::{BTreeMap, BTreeSet, HashMap, VecDeque};
use super::depset::{DepSetMember, DepSetRecord};
use super::{crates, npm, pip, PullIntake, SourceRt, Want};
use crate::promote::intake::IntakeChain;
use traits::ArtifactId;
/// The most members one closure brings in; past it the set is held.
pub const MAX_MEMBERS: usize = 4_000;
// ── semver: npm ranges and cargo requirements ─────────────────────────────
/// `1.2.3-beta.1+build` → `(1, 2, 3, ["beta", "1"])`.
pub fn parse_semver(v: &str) -> Option<(u64, u64, u64, Vec<String>)> {
let v = v.trim().trim_start_matches(['v', '=']);
let v = v.split('+').next()?;
let (core, pre) = match v.split_once('-') {
Some((c, p)) => (c, p.split('.').map(str::to_string).collect()),
None => (v, Vec::new()),
};
let mut it = core.split('.');
let a = it.next()?.parse().ok()?;
let b = it.next()?.parse().ok()?;
let c = it.next()?.parse().ok()?;
if it.next().is_some() {
return None;
}
Some((a, b, c, pre))
}
/// semver precedence.
pub fn semver_cmp(a: &str, b: &str) -> Ordering {
match (parse_semver(a), parse_semver(b)) {
(Some(x), Some(y)) => {
let o = (x.0, x.1, x.2).cmp(&(y.0, y.1, y.2));
if o != Ordering::Equal {
return o;
}
match (x.3.is_empty(), y.3.is_empty()) {
(true, true) => Ordering::Equal,
(true, false) => Ordering::Greater,
(false, true) => Ordering::Less,
(false, false) => {
for (p, q) in x.3.iter().zip(y.3.iter()) {
let o = match (p.parse::<u64>(), q.parse::<u64>()) {
(Ok(m), Ok(n)) => m.cmp(&n),
(Ok(_), Err(_)) => Ordering::Less,
(Err(_), Ok(_)) => Ordering::Greater,
_ => p.cmp(q),
};
if o != Ordering::Equal {
return o;
}
}
x.3.len().cmp(&y.3.len())
}
}
}
(Some(_), None) => Ordering::Greater,
(None, Some(_)) => Ordering::Less,
(None, None) => a.cmp(b),
}
}
/// A partial version (`1`, `1.2`, `1.x`, `*`): the numbers given.
fn partial(v: &str) -> Option<(Vec<u64>, Vec<String>)> {
let v = v.trim().trim_start_matches(['v', '=']);
let v = v.split('+').next().unwrap_or(v);
let (core, pre) = match v.split_once('-') {
Some((c, p)) => (c, p.split('.').map(str::to_string).collect()),
None => (v, Vec::new()),
};
let mut nums = Vec::new();
for p in core.split('.') {
if p == "x" || p == "X" || p == "*" || p.is_empty() {
break;
}
nums.push(p.parse().ok()?);
}
if nums.len() > 3 {
return None;
}
Some((nums, pre))
}
fn ver(n: &[u64], pre: &[String]) -> String {
let g = |i: usize| n.get(i).copied().unwrap_or(0);
let mut s = format!("{}.{}.{}", g(0), g(1), g(2));
if !pre.is_empty() {
s.push('-');
s.push_str(&pre.join("."));
}
s
}
/// One comparator set as `(op, version)` pairs, every one of which must hold.
fn comparators(set: &str, cargo: bool) -> Option<Vec<(&'static str, String)>> {
let set = set.trim();
let mut out = Vec::new();
if set.is_empty() || set == "*" || set == "x" || set == "latest" {
return Some(out);
}
// Hyphen range: `1.2 - 2.3`.
if let Some((lo, hi)) = set.split_once(" - ") {
let (l, lp) = partial(lo)?;
let (h, hp) = partial(hi)?;
out.push((">=", ver(&l, &lp)));
match h.len() {
0 => {}
1 => out.push(("<", ver(&[h[0] + 1], &[]))),
2 => out.push(("<", ver(&[h[0], h[1] + 1], &[]))),
_ => out.push(("<=", ver(&h, &hp))),
}
return Some(out);
}
let tokens: Vec<String> = if cargo {
set.split(',').map(|t| t.trim().replace(' ', "")).collect()
} else {
// `>= 1.2` is one comparator: join an operator with the version after it.
let mut t: Vec<String> = Vec::new();
for w in set.split_whitespace() {
match t.last_mut() {
Some(l) if matches!(l.as_str(), ">" | ">=" | "<" | "<=" | "=" | "^" | "~") => {
l.push_str(w)
}
_ => t.push(w.to_string()),
}
}
t
};
for t in tokens.iter().filter(|t| !t.is_empty()) {
let (op, rest) = ["<=", ">=", "~>", "<", ">", "=", "^", "~"]
.iter()
.find_map(|op| t.strip_prefix(op).map(|r| (*op, r)))
.unwrap_or(("", t.as_str()));
let (n, pre) = partial(rest)?;
let caret = |n: &[u64]| -> (String, String) {
let lo = ver(n, &pre);
let hi = match n {
[] => return (lo, String::new()),
[0] => ver(&[1], &[]),
[0, 0] => ver(&[0, 1], &[]),
[0, b] => ver(&[0, b + 1], &[]),
[0, 0, c] => ver(&[0, 0, c + 1], &[]),
[0, b, _] => ver(&[0, b + 1], &[]),
[a, ..] => ver(&[a + 1], &[]),
};
(lo, hi)
};
let tilde = |n: &[u64]| -> (String, String) {
let lo = ver(n, &pre);
let hi = match n {
[] => String::new(),
[a] => ver(&[a + 1], &[]),
[a, b, ..] => ver(&[*a, b + 1], &[]),
};
(lo, hi)
};
let range = |lo: String, hi: String, out: &mut Vec<(&'static str, String)>| {
out.push((">=", lo));
if !hi.is_empty() {
out.push(("<", hi));
}
};
match op {
"^" => {
let (lo, hi) = caret(&n);
range(lo, hi, &mut out)
}
"~" | "~>" => {
let (lo, hi) = tilde(&n);
range(lo, hi, &mut out)
}
"" if cargo => {
let (lo, hi) = caret(&n);
range(lo, hi, &mut out)
}
"" | "=" => match n.len() {
// An x-range: `1`, `1.2`, `1.x`.
0 => {}
1 => range(ver(&n, &[]), ver(&[n[0] + 1], &[]), &mut out),
2 => range(ver(&n, &[]), ver(&[n[0], n[1] + 1], &[]), &mut out),
_ => out.push(("=", ver(&n, &pre))),
},
">" if n.len() < 3 => {
let up = if n.len() == 1 {
vec![n[0] + 1]
} else {
vec![n[0], n[1] + 1]
};
out.push((">=", ver(&up, &[])))
}
"<=" if n.len() < 3 => {
let up = if n.len() == 1 {
vec![n[0] + 1]
} else {
vec![n[0], n[1] + 1]
};
out.push(("<", ver(&up, &[])))
}
">" => out.push((">", ver(&n, &pre))),
">=" => out.push((">=", ver(&n, &pre))),
"<" => out.push(("<", ver(&n, &pre))),
"<=" => out.push(("<=", ver(&n, &pre))),
_ => return None,
}
}
Some(out)
}
/// **Does `version` satisfy `range`?** npm's grammar (`||`, spaces, `^`, `~`, x-ranges,
/// hyphens) or cargo's (`,`, a bare version is `^`). A pre-release satisfies only a
/// range that names a pre-release of the same `major.minor.patch`.
pub fn satisfies(range: &str, version: &str, cargo: bool) -> bool {
let Some(v) = parse_semver(version) else {
return false;
};
let sets: Vec<&str> = if cargo {
vec![range]
} else {
range.split("||").collect()
};
sets.into_iter().any(|set| {
let Some(cs) = comparators(set, cargo) else {
return false;
};
if !v.3.is_empty()
&& !cs.iter().any(|(_, c)| {
parse_semver(c)
.is_some_and(|p| !p.3.is_empty() && (p.0, p.1, p.2) == (v.0, v.1, v.2))
})
{
return false;
}
cs.iter().all(|(op, c)| {
let o = semver_cmp(version, c);
match *op {
"=" => o == Ordering::Equal,
">" => o == Ordering::Greater,
">=" => o != Ordering::Less,
"<" => o == Ordering::Less,
"<=" => o != Ordering::Greater,
_ => false,
}
})
})
}
/// The highest of `versions` that satisfies `range`.
pub fn best<'a>(
range: &str,
versions: impl Iterator<Item = &'a str>,
cargo: bool,
) -> Option<String> {
versions
.filter(|v| satisfies(range, v, cargo))
.max_by(|a, b| semver_cmp(a, b))
.map(str::to_string)
}
// ── PEP 440, PEP 508 and markers ───────────────────────────────────────────
/// A PEP 440 version, comparable.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct PyVer {
epoch: u64,
release: Vec<u64>,
/// `(phase, n)`: dev-only releases sort first, then a, b, rc, then the final.
pre: (u8, u64),
post: Option<u64>,
dev: Option<u64>,
}
impl PyVer {
pub fn is_final(&self) -> bool {
self.pre.0 == 4 && self.dev.is_none()
}
}
/// Read a PEP 440 version (`1.0`, `2.0rc1`, `1!2.0.post1.dev3`).
pub fn py_version(v: &str) -> Option<PyVer> {
let v = v.trim().to_ascii_lowercase();
let v = v.trim_start_matches('v');
let v = v.split('+').next()?;
let (epoch, rest) = match v.split_once('!') {
Some((e, r)) => (e.parse().ok()?, r),
None => (0, v),
};
let mut i = 0;
let b = rest.as_bytes();
while i < b.len() && (b[i].is_ascii_digit() || b[i] == b'.') {
i += 1;
}
let release: Vec<u64> = rest[..i]
.trim_end_matches('.')
.split('.')
.map(|p| p.parse().ok())
.collect::<Option<_>>()?;
let mut tail = rest[i..].trim_start_matches(['.', '-', '_']).to_string();
let num = |t: &mut String| -> u64 {
let t2 = t.trim_start_matches(['.', '-', '_']);
let d: String = t2.chars().take_while(|c| c.is_ascii_digit()).collect();
*t = t2[d.len()..]
.trim_start_matches(['.', '-', '_'])
.to_string();
d.parse().unwrap_or(0)
};
let mut pre = (4u8, 0u64);
for (p, rank) in [
("alpha", 1),
("beta", 2),
("preview", 3),
("pre", 3),
("rc", 3),
("a", 1),
("b", 2),
("c", 3),
] {
if let Some(r) = tail.strip_prefix(p) {
tail = r.to_string();
pre = (rank, num(&mut tail));
break;
}
}
let mut post = None;
for p in ["post", "rev", "r"] {
if let Some(r) = tail.strip_prefix(p) {
tail = r.to_string();
post = Some(num(&mut tail));
break;
}
}
let mut dev = None;
if let Some(r) = tail.strip_prefix("dev") {
tail = r.to_string();
dev = Some(num(&mut tail));
}
if !tail.is_empty() {
return None;
}
// A dev release of a final (`1.0.dev1`) sorts before its pre-releases.
if dev.is_some() && pre.0 == 4 && post.is_none() {
pre = (0, 0);
}
let mut release = release;
while release.len() > 1 && release.last() == Some(&0) {
release.pop();
}
Some(PyVer {
epoch,
release,
pre,
post,
dev: dev.map(|d| d + 1),
})
}
fn py_cmp(a: &PyVer, b: &PyVer) -> Ordering {
let dev = |d: Option<u64>| d.unwrap_or(u64::MAX);
(
a.epoch,
&a.release,
a.pre,
a.post.map(|p| p + 1).unwrap_or(0),
dev(a.dev),
)
.cmp(&(
b.epoch,
&b.release,
b.pre,
b.post.map(|p| p + 1).unwrap_or(0),
dev(b.dev),
))
}
/// **Does `version` satisfy a PEP 440 specifier** (`>=2.0,<3`, `~=1.4.2`, `==1.*`)?
pub fn py_satisfies(spec: &str, version: &str) -> bool {
let Some(v) = py_version(version) else {
return false;
};
spec.split(',')
.map(str::trim)
.filter(|s| !s.is_empty())
.all(|c| {
let (op, rest) = ["===", "~=", "==", "!=", ">=", "<=", ">", "<"]
.iter()
.find_map(|op| c.strip_prefix(op).map(|r| (*op, r.trim())))
.unwrap_or(("==", c));
if op == "===" {
return rest == version;
}
if let Some(prefix) = rest.strip_suffix(".*") {
let Some(p) = py_version(prefix) else {
return false;
};
let m = v.epoch == p.epoch
&& v.release.len() >= p.release.len().min(v.release.len())
&& p.release
.iter()
.enumerate()
.all(|(i, n)| v.release.get(i).copied().unwrap_or(0) == *n);
return if op == "!=" { !m } else { m };
}
let Some(w) = py_version(rest) else {
return false;
};
let o = py_cmp(&v, &w);
match op {
"==" => o == Ordering::Equal,
"!=" => o != Ordering::Equal,
">=" => o != Ordering::Less,
"<=" => o != Ordering::Greater,
">" => o == Ordering::Greater,
"<" => o == Ordering::Less,
"~=" => {
if o == Ordering::Less || w.release.len() < 2 {
return false;
}
let n = w.release.len() - 1;
v.release.len() >= n && v.release[..n] == w.release[..n]
|| (v.release.len() < n
&& w.release[..n]
.iter()
.enumerate()
.all(|(i, x)| v.release.get(i).copied().unwrap_or(0) == *x))
}
_ => false,
}
})
}
/// The environment markers are judged in: CPython 3.12 on x86_64 Linux, no extra.
fn marker_env(var: &str) -> Option<&'static str> {
Some(match var {
"python_version" => "3.12",
"python_full_version" => "3.12.0",
"os_name" => "posix",
"sys_platform" => "linux",
"platform_system" => "Linux",
"platform_machine" => "x86_64",
"platform_python_implementation" => "CPython",
"implementation_name" => "cpython",
"implementation_version" => "3.12.0",
"platform_release" | "platform_version" => "",
"extra" => "",
_ => return None,
})
}
/// **Does a PEP 508 marker hold** in [`marker_env`]? An unreadable marker holds (the
/// dependency is pulled: more is scanned, nothing is missed).
pub fn marker_holds(m: &str) -> bool {
let toks = marker_tokens(m);
let mut p = MarkerParser { t: &toks, i: 0 };
match p.or() {
Some(v) if p.i == toks.len() => v,
_ => true,
}
}
fn marker_tokens(m: &str) -> Vec<String> {
let mut out = Vec::new();
let c: Vec<char> = m.chars().collect();
let mut i = 0;
while i < c.len() {
let ch = c[i];
if ch.is_whitespace() {
i += 1;
} else if ch == '(' || ch == ')' {
out.push(ch.to_string());
i += 1;
} else if ch == '"' || ch == '\'' {
let mut j = i + 1;
while j < c.len() && c[j] != ch {
j += 1;
}
out.push(format!(
"\"{}",
c[i + 1..j.min(c.len())].iter().collect::<String>()
));
i = j + 1;
} else if "<>=!~".contains(ch) {
let mut j = i;
while j < c.len() && "<>=!~".contains(c[j]) {
j += 1;
}
out.push(c[i..j].iter().collect());
i = j;
} else {
let mut j = i;
while j < c.len() && !c[j].is_whitespace() && !"()<>=!~\"'".contains(c[j]) {
j += 1;
}
out.push(c[i..j].iter().collect());
i = j;
}
}
// `not in` is one operator.
let mut merged: Vec<String> = Vec::new();
for t in out {
if t == "in" && merged.last().is_some_and(|l| l == "not") {
merged.pop();
merged.push("not in".into());
} else {
merged.push(t);
}
}
merged
}
struct MarkerParser<'a> {
t: &'a [String],
i: usize,
}
impl MarkerParser<'_> {
fn peek(&self) -> Option<&str> {
self.t.get(self.i).map(String::as_str)
}
fn or(&mut self) -> Option<bool> {
let mut v = self.and()?;
while self.peek() == Some("or") {
self.i += 1;
let r = self.and()?;
v = v || r;
}
Some(v)
}
fn and(&mut self) -> Option<bool> {
let mut v = self.atom()?;
while self.peek() == Some("and") {
self.i += 1;
let r = self.atom()?;
v = v && r;
}
Some(v)
}
fn value(&mut self) -> Option<(String, bool)> {
let t = self.t.get(self.i)?.clone();
self.i += 1;
if let Some(s) = t.strip_prefix('"') {
Some((s.to_string(), false))
} else {
Some((marker_env(&t)?.to_string(), t.contains("version")))
}
}
fn atom(&mut self) -> Option<bool> {
if self.peek() == Some("(") {
self.i += 1;
let v = self.or()?;
if self.peek() != Some(")") {
return None;
}
self.i += 1;
return Some(v);
}
let (l, lv) = self.value()?;
let op = self.t.get(self.i)?.clone();
self.i += 1;
let (r, rv) = self.value()?;
let versions = lv || rv;
Some(match op.as_str() {
"in" => r.contains(&l),
"not in" => !r.contains(&l),
"==" | "!=" | "<" | "<=" | ">" | ">=" | "~=" | "===" if versions => {
let (var, lit, op) = if lv { (l, r, op) } else { (r, l, flip(&op)) };
if var.is_empty() {
false
} else {
py_satisfies(&format!("{op}{lit}"), &var)
}
}
"==" | "===" => l == r,
"!=" => l != r,
_ => l == r,
})
}
}
fn flip(op: &str) -> String {
match op {
"<" => ">",
">" => "<",
"<=" => ">=",
">=" => "<=",
o => o,
}
.to_string()
}
/// One `Requires-Dist`: `(normalized name, specifier)`, `None` when its marker does not
/// hold (or it needs an extra).
pub fn requirement(line: &str) -> Option<(String, String)> {
let (req, marker) = match line.split_once(';') {
Some((r, m)) => (r.trim(), Some(m.trim())),
None => (line.trim(), None),
};
if marker.is_some_and(|m| !marker_holds(m)) {
return None;
}
let end = req
.find(|c: char| !(c.is_ascii_alphanumeric() || c == '-' || c == '_' || c == '.'))
.unwrap_or(req.len());
if end == 0 {
return None;
}
let name = crate::promote::intake::normalize_project(&req[..end]);
let mut rest = req[end..].trim();
if rest.starts_with('[') {
rest = rest.split_once(']').map(|(_, r)| r.trim()).unwrap_or("");
}
let spec = rest
.trim_start_matches('(')
.trim_end_matches(')')
.trim()
.to_string();
if spec.starts_with('@') {
// A direct URL: no index version satisfies it.
return Some((name, spec));
}
Some((name, spec))
}
/// The `Requires-Dist` lines of a core-metadata document.
pub fn requires_dist(metadata: &str) -> Vec<String> {
let mut out = Vec::new();
for l in metadata.lines() {
if l.is_empty() {
break; // the body (the long description) starts here
}
if let Some(v) = l.strip_prefix("Requires-Dist:") {
out.push(v.trim().to_string());
}
}
out
}
// ── the walks ──────────────────────────────────────────────────────────────
/// A walk's result: the drives, each member's role and what needed it, what could not
/// be resolved, notes.
#[derive(Default)]
pub(super) struct Walked {
pub drives: Vec<(String, String, bool)>,
pub roles: HashMap<String, (String, String)>,
pub unresolved: Vec<(String, String)>,
pub notes: Vec<String>,
}
impl Walked {
fn push(&mut self, d: (String, String, bool), role: &str, via: &str) {
self.roles
.insert(d.0.clone(), (role.to_string(), via.to_string()));
self.drives.push(d);
}
}
impl PullIntake {
/// Record a walk as ONE set and the want's outcome.
pub(super) fn record_walk(
&self,
src: &SourceRt,
want: &Want,
root: String,
w: Walked,
) -> String {
let roles = w.roles;
let mut unresolved = w.unresolved;
unresolved.sort();
unresolved.dedup();
let members: Vec<DepSetMember> = super::depset::members_of(&w.drives, &|n: &str| {
roles.get(n).cloned().unwrap_or_default()
});
let rec = DepSetRecord {
id: super::depset::set_id(&src.cfg.name, want),
source: src.cfg.name.clone(),
ecosystem: src.cfg.kind.name().into(),
root,
want: want.clone(),
at: super::now_secs(),
members,
unresolved,
notes: w.notes,
};
self.record_set(&rec);
self.record_drives(&src.cfg.name, want, w.drives)
}
/// **npm**: the closure of `package@version`, from the packuments.
pub(super) fn npm_walk(
&self,
chain: &IntakeChain,
src: &SourceRt,
package: &str,
version: &str,
root_doc: serde_json::Value,
) -> anyhow::Result<Walked> {
let mut w = Walked::default();
let mut docs: HashMap<String, Option<serde_json::Value>> = HashMap::new();
docs.insert(package.to_string(), Some(root_doc));
let mut seen = BTreeSet::new();
let mut q: VecDeque<(String, String, String)> = VecDeque::new();
q.push_back((package.into(), version.into(), String::new()));
seen.insert(format!("{package}@{version}"));
let base = src.cfg.url.trim_end_matches('/').to_string();
let (http, auth, cap) = (self.http.as_ref(), src.auth(), src.cap());
while let Some((pkg, v, via)) = q.pop_front() {
if w.drives.len() >= MAX_MEMBERS {
w.unresolved.push((
format!("{pkg}@{v}"),
format!("the closure has more than {MAX_MEMBERS} members; held"),
));
break;
}
let doc = match docs.get(&pkg) {
Some(d) => d.clone(),
None => {
let d = npm::packument(http, &src.cfg.url, &pkg, auth)?;
if let Some(d) = &d {
self.remember_npm_listing(&src.cfg.name, &pkg, d);
}
docs.insert(pkg.clone(), d.clone());
d
}
};
let Some(doc) = doc else {
w.unresolved.push((
format!("{pkg}@{v}"),
format!("source '{}' does not publish '{pkg}'", src.cfg.name),
));
continue;
};
let page = format!("{base}/{}", npm::url_name(&pkg));
let Some(rv) = npm::version(&doc, &page, &pkg, &v) else {
w.unresolved.push((
format!("{pkg}@{v}"),
format!("source '{}' does not publish {pkg}@{v}", src.cfg.name),
));
continue;
};
let id = npm::id(&src.cfg.name, &pkg, &v);
let d = self.drive(chain, src, &id, || npm::fetch_version(http, &rv, auth, cap))?;
w.push(
d,
if via.is_empty() {
"requested"
} else {
"dependency"
},
&via,
);
let me = format!("{pkg}@{v}");
let manifest = doc
.pointer(&format!(
"/versions/{}",
v.replace('~', "~0").replace('/', "~1")
))
.cloned()
.unwrap_or_default();
let peer_optional = |n: &str| {
manifest
.pointer(&format!(
"/peerDependenciesMeta/{}/optional",
n.replace('~', "~0").replace('/', "~1")
))
.and_then(|o| o.as_bool())
.unwrap_or(false)
};
let mut wants: BTreeMap<String, (String, bool)> = BTreeMap::new();
for (field, optional) in [
("dependencies", false),
("optionalDependencies", true),
("peerDependencies", false),
] {
if let Some(m) = manifest.get(field).and_then(|m| m.as_object()) {
for (n, r) in m {
if field == "peerDependencies" && peer_optional(n) {
continue;
}
let r = r.as_str().unwrap_or("*").to_string();
wants.entry(n.clone()).or_insert((r, optional));
}
}
}
for (name, (range, optional)) in wants {
let (dep, range) = match range.strip_prefix("npm:") {
Some(alias) => match alias.rsplit_once('@').filter(|(n, _)| !n.is_empty()) {
Some((n, r)) => (n.to_string(), r.to_string()),
None => (alias.to_string(), "*".to_string()),
},
None => (name.clone(), range),
};
let not_registry = range.contains("://")
|| range.starts_with("git")
|| range.starts_with("file:")
|| range.starts_with("link:")
|| (range.contains('/') && !range.starts_with('@'));
let hold = |w: &mut Walked, why: String| {
if optional {
w.notes.push(format!(
"{dep}@{range} (optional, needed by {me}) is left out: {why}"
));
} else {
w.unresolved
.push((format!("{dep}@{range}"), format!("{why} (needed by {me})")));
}
};
if not_registry {
hold(&mut w, "it is not a registry version".into());
continue;
}
let d = match docs.get(&dep) {
Some(d) => d.clone(),
None => {
let d = npm::packument(http, &src.cfg.url, &dep, auth)?;
if let Some(d) = &d {
self.remember_npm_listing(&src.cfg.name, &dep, d);
}
docs.insert(dep.clone(), d.clone());
d
}
};
let Some(d) = d else {
hold(
&mut w,
format!("source '{}' does not publish '{dep}'", src.cfg.name),
);
continue;
};
let latest = npm::latest(&d).filter(|l| satisfies(&range, l, false));
let pick = latest.or_else(|| {
d.get("versions")
.and_then(|v| v.as_object())
.and_then(|vs| best(&range, vs.keys().map(String::as_str), false))
});
match pick {
Some(p) => {
if seen.insert(format!("{dep}@{p}")) {
q.push_back((dep, p, me.clone()));
}
}
None => hold(&mut w, format!("no version of '{dep}' satisfies {range}")),
}
}
}
Ok(w)
}
/// **cargo**: the closure of `name version`, from the sparse index.
pub(super) fn crate_walk(
&self,
chain: &IntakeChain,
src: &SourceRt,
root: crates::IndexLine,
root_lines: Vec<crates::IndexLine>,
) -> anyhow::Result<Walked> {
let mut w = Walked::default();
let mut index: HashMap<String, Option<Vec<crates::IndexLine>>> = HashMap::new();
index.insert(root.name.to_ascii_lowercase(), Some(root_lines));
let mut seen = BTreeSet::new();
seen.insert(format!("{}@{}", root.name.to_ascii_lowercase(), root.vers));
let mut q: VecDeque<(crates::IndexLine, String)> = VecDeque::new();
q.push_back((root, String::new()));
while let Some((line, via)) = q.pop_front() {
if w.drives.len() >= MAX_MEMBERS {
w.unresolved.push((
format!("{}@{}", line.name, line.vers),
format!("the closure has more than {MAX_MEMBERS} members; held"),
));
break;
}
let d = self.drive_crate_line(chain, src, &line)?;
w.push(
d,
if via.is_empty() {
"requested"
} else {
"dependency"
},
&via,
);
let me = format!("{}@{}", line.name, line.vers);
let deps = line
.raw
.get("deps")
.and_then(|d| d.as_array())
.cloned()
.unwrap_or_default();
for dep in deps {
let s = |k: &str| dep.get(k).and_then(|v| v.as_str()).map(str::to_string);
if s("kind").as_deref() == Some("dev")
|| dep
.get("optional")
.and_then(|o| o.as_bool())
.unwrap_or(false)
|| dep.get("registry").is_some_and(|r| !r.is_null())
{
continue;
}
let Some(name) = s("package").or_else(|| s("name")) else {
continue;
};
let req = s("req").unwrap_or_else(|| "*".into());
let key = name.to_ascii_lowercase();
if !index.contains_key(&key) {
let lines = crates::index(self.http.as_ref(), &src.cfg.url, &name, src.auth())?;
if let Some(l) = &lines {
self.remember_listing_crate(&src.cfg.name, &name, l);
}
index.insert(key.clone(), lines);
}
let Some(lines) = index.get(&key).cloned().flatten() else {
w.unresolved.push((
format!("{name} {req}"),
format!(
"source '{}' does not publish crate '{name}' (needed by {me})",
src.cfg.name
),
));
continue;
};
let live: Vec<&str> = lines
.iter()
.filter(|l| !l.yanked)
.map(|l| l.vers.as_str())
.collect();
match best(&req, live.into_iter(), true) {
Some(v) => {
if seen.insert(format!("{key}@{v}")) {
if let Some(l) = lines.iter().find(|l| l.vers == v) {
q.push_back((l.clone(), me.clone()));
}
}
}
None => w.unresolved.push((
format!("{name} {req}"),
format!("no unyanked version of '{name}' satisfies {req} (needed by {me})"),
)),
}
}
}
Ok(w)
}
/// **What a pulled wheel requires**, read in a [`super::manifest_job::WHEEL_REQUIRES`] job
/// (SEC-D3, lane HOL-312-HARDEN): from PEP 658's `<url>.metadata`, else the wheel's own
/// `*.dist-info/METADATA`; this process parses neither. `Ok(None)`: no core metadata.
fn wheel_requires(
&self,
chain: &IntakeChain,
src: &SourceRt,
f: &pip::RemoteFile,
id: &ArtifactId,
) -> Result<Option<Vec<(String, String)>>, String> {
use super::manifest_job as mj;
let pep658 = self
.http
.get(
&format!("{}.metadata", f.url),
&[],
src.auth(),
16 * 1024 * 1024,
)
.ok()
.filter(|r| r.status == 200)
.map(|r| r.body);
let (name, bytes) = match pep658 {
Some(b) => (mj::METADATA_FILE, b),
None => match chain
.incoming_artifact(id)
.ok()
.or_else(|| chain.serve(id).ok().flatten())
{
Some(b) => (mj::WHEEL_FILE, b),
None => return Ok(None),
},
};
let a: mj::WheelAnswer = mj::run_job(
chain,
&self.root,
mj::WHEEL_REQUIRES,
&[(name.into(), &bytes)],
)
.map_err(|e| format!("{e:#}"))?;
Ok(a.found.then_some(a.requires))
}
/// **Python**: the files chosen for the request, then each wheel's `Requires-Dist`.
pub(super) fn pip_walk(
&self,
chain: &IntakeChain,
src: &SourceRt,
project: &str,
chosen: Vec<pip::RemoteFile>,
) -> anyhow::Result<Walked> {
let mut w = Walked::default();
let select = if src.cfg.select.is_empty() {
pip::default_select()
} else {
src.cfg.select.clone()
};
let max = src.cfg.max_files.unwrap_or(8);
let mut seen = BTreeSet::new();
let mut q: VecDeque<(String, Vec<pip::RemoteFile>, String)> = VecDeque::new();
if let Some(v) = chosen.first().and_then(|f| pip::version_of(&f.filename)) {
seen.insert(format!("{project}=={v}"));
}
q.push_back((project.to_string(), chosen, String::new()));
while let Some((proj, files, via)) = q.pop_front() {
if w.drives.len() >= MAX_MEMBERS {
w.unresolved.push((
proj.clone(),
format!("the closure has more than {MAX_MEMBERS} members; held"),
));
break;
}
let version = files
.first()
.and_then(|f| pip::version_of(&f.filename))
.unwrap_or_default();
let me = format!("{proj}=={version}");
let mut reqs: Vec<(String, String)> = Vec::new();
let mut read_meta = false;
for f in &files {
let id = super::pip_id(&src.cfg.name, &f.filename);
let (line, refused) = self.drive_pip(chain, src, &id, f)?;
w.push(
(id.name.clone(), line, refused),
if via.is_empty() {
"requested"
} else {
"dependency"
},
&via,
);
if !read_meta && !refused && f.filename.to_ascii_lowercase().ends_with(".whl") {
match self.wheel_requires(chain, src, f, &id) {
Ok(Some(r)) => {
reqs = r;
read_meta = true;
}
Ok(None) => {}
// Fail closed: a wheel whose metadata no job read holds the set.
Err(e) => {
w.unresolved.push((
me.clone(),
format!("the metadata of {} was not read: {e}", f.filename),
));
read_meta = true;
}
}
}
}
if !read_meta {
w.notes.push(format!(
"{me}: no wheel metadata was read, so its dependencies are not known"
));
}
for (dep, spec) in reqs {
if spec.starts_with('@') {
w.unresolved.push((
format!("{dep} {spec}"),
format!("a direct URL is not an index version (needed by {me})"),
));
continue;
}
let Some(all) =
pip::project_files(self.http.as_ref(), &src.cfg.url, &dep, src.auth())?
else {
w.unresolved.push((
format!("{dep} {spec}"),
format!(
"source '{}' does not publish '{dep}' (needed by {me})",
src.cfg.name
),
));
continue;
};
self.remember_listing_pip(&src.cfg.name, &dep, &all);
let mut versions: Vec<(PyVer, String)> = all
.iter()
.filter(|f| !f.yanked && f.sha256.is_some())
.filter_map(|f| pip::version_of(&f.filename))
.filter_map(|v| py_version(&v).map(|p| (p, v)))
.filter(|(p, v)| p.is_final() && py_satisfies(&spec, v))
.collect();
versions.sort_by(|a, b| py_cmp(&a.0, &b.0));
let Some((_, pick)) = versions.pop() else {
w.unresolved.push((
format!("{dep} {spec}"),
format!("no final release of '{dep}' satisfies '{spec}' (needed by {me})"),
));
continue;
};
if !seen.insert(format!("{dep}=={pick}")) {
continue;
}
let of_version: Vec<pip::RemoteFile> = all
.iter()
.filter(|f| pip::version_of(&f.filename).as_deref() == Some(pick.as_str()))
.cloned()
.collect();
let files = pip::newest_release(&of_version, &select, max);
if files.is_empty() {
w.unresolved.push((format!("{dep}=={pick}"), format!("source '{}' publishes no file of it this source selects (needed by {me})", src.cfg.name)));
continue;
}
q.push_back((dep, files, me.clone()));
}
}
Ok(w)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn npm_ranges_resolve_as_npm_does() {
let vs = [
"1.0.0",
"1.2.3",
"1.9.0",
"2.0.0",
"2.1.0-beta.1",
"0.2.5",
"0.3.0",
];
let b = |r: &str| best(r, vs.iter().copied(), false);
assert_eq!(b("^1.2.0").as_deref(), Some("1.9.0"));
assert_eq!(b("~1.2.0").as_deref(), Some("1.2.3"));
assert_eq!(b("1.x").as_deref(), Some("1.9.0"));
assert_eq!(b(">=1.0.0 <2.0.0").as_deref(), Some("1.9.0"));
assert_eq!(b("^0.2.1").as_deref(), Some("0.2.5"));
assert_eq!(b("1.0.0 - 1.5").as_deref(), Some("1.2.3"));
assert_eq!(b("^1.0.0 || ^2.0.0").as_deref(), Some("2.0.0"));
assert_eq!(b("*").as_deref(), Some("2.0.0"));
assert_eq!(b("2.0.0").as_deref(), Some("2.0.0"));
assert_eq!(b("^2.1.0-beta.0").as_deref(), Some("2.1.0-beta.1"));
assert_eq!(b("^3"), None);
}
#[test]
fn cargo_requirements_resolve_as_cargo_does() {
let vs = ["0.4.1", "0.4.9", "0.5.0", "1.0.0", "1.0.200", "1.1.0"];
let b = |r: &str| best(r, vs.iter().copied(), true);
assert_eq!(b("1.0").as_deref(), Some("1.1.0"));
assert_eq!(b("0.4").as_deref(), Some("0.4.9"));
assert_eq!(b("=1.0.0").as_deref(), Some("1.0.0"));
assert_eq!(b(">=0.4, <0.5").as_deref(), Some("0.4.9"));
assert_eq!(b("~1.0").as_deref(), Some("1.0.200"));
assert_eq!(b("*").as_deref(), Some("1.1.0"));
}
#[test]
fn python_specifiers_and_markers_hold_as_pip_judges_them() {
assert!(py_satisfies(">=2.17,<3", "2.32.3"));
assert!(!py_satisfies(">=2.17,<3", "3.0"));
assert!(py_satisfies("~=1.4.2", "1.4.9"));
assert!(!py_satisfies("~=1.4.2", "1.5.0"));
assert!(py_satisfies("==1.*", "1.26.4"));
assert!(py_satisfies("!=1.25.0,>=1.21.1", "2.2.3"));
assert!(py_satisfies("", "1.0"));
assert!(py_version("2.0rc1").unwrap() < py_version("2.0").unwrap());
assert!(!py_version("2.0rc1").unwrap().is_final());
assert_eq!(
requirement("charset-normalizer<4,>=2"),
Some(("charset-normalizer".into(), "<4,>=2".into()))
);
assert_eq!(
requirement("PySocks!=1.5.7,>=1.5.6; extra == \"socks\""),
None
);
assert_eq!(requirement("colorama; sys_platform == \"win32\""), None);
assert_eq!(
requirement("importlib-metadata>=4.6; python_version < \"3.10\""),
None
);
assert_eq!(
requirement("typing_extensions>=4; python_version >= \"3.8\""),
Some(("typing-extensions".into(), ">=4".into()))
);
assert_eq!(
requirement("idna (<4,>=2.5)"),
Some(("idna".into(), "<4,>=2.5".into()))
);
assert_eq!(
requires_dist("Name: x\nRequires-Dist: a>=1\nRequires-Dist: b ; extra == 'x'\n\nRequires-Dist: body"),
vec!["a>=1".to_string(), "b ; extra == 'x'".to_string()]
);
}
}