Skip to content

g1t/crates/scan/src/graph.rs

476 lines20,019 bytesCodeBlame
1//! A repository's dependency graph, as its lockfiles state it: every
2//! package each lockfile resolves, whether the project asks for it itself
3//! (direct) or gets it through another package (transitive), whether it is
4//! for development only, and its license when the lockfile records one.
5//!
6//! Lockfiles differ in what they say. `package-lock.json`, `pnpm-lock.yaml`,
7//! `Cargo.lock` and `go.mod` name the project's own dependencies; a
8//! `requirements.txt` lists what is installed, and from pip-compile says
9//! which came from where. `yarn.lock`, `go.sum` and `poetry.lock` do not
10//! say, so their packages are [`Relationship::Unknown`].
11
12use std::collections::{BTreeMap, BTreeSet};
13
14use serde::{Deserialize, Serialize};
15use serde_json::Value;
16
17use crate::lockfiles::{Ecosystem, Lockfile, Package};
18
19/// How the project comes to depend on a package.
20#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
21#[serde(rename_all = "lowercase")]
22pub enum Relationship {
23 Direct,
24 Transitive,
25 /// The lockfile does not say.
26 Unknown,
27}
28
29impl Relationship {
30 pub fn as_str(self) -> &'static str {
31 match self {
32 Relationship::Direct => "direct",
33 Relationship::Transitive => "transitive",
34 Relationship::Unknown => "unknown",
35 }
36 }
37
38 pub fn parse(text: &str) -> Relationship {
39 match text {
40 "direct" => Relationship::Direct,
41 "transitive" => Relationship::Transitive,
42 _ => Relationship::Unknown,
43 }
44 }
45}
46
47/// One package in one lockfile.
48#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
49pub struct Dependency {
50 pub package: Package,
51 /// The lockfile, from the repository's root.
52 pub manifest: String,
53 pub relationship: Relationship,
54 /// For development or tests only, when the lockfile says so.
55 pub development: bool,
56 /// An SPDX license expression, when the lockfile records one.
57 pub license: Option<String>,
58}
59
60impl Dependency {
61 /// The package URL (purl) that names it everywhere: `pkg:npm/%40babel/core@7.0.0`.
62 pub fn purl(&self) -> String {
63 purl(self.package.ecosystem, &self.package.name, &self.package.version)
64 }
65}
66
67/// The purl type for an ecosystem.
68pub fn purl_type(ecosystem: Ecosystem) -> &'static str {
69 match ecosystem {
70 Ecosystem::Npm => "npm",
71 Ecosystem::Cargo => "cargo",
72 Ecosystem::Go => "golang",
73 Ecosystem::PyPI => "pypi",
74 }
75}
76
77fn purl_encode(text: &str) -> String {
78 text.chars()
79 .map(|c| match c {
80 '@' => "%40".to_owned(),
81 ' ' => "%20".to_owned(),
82 '?' => "%3F".to_owned(),
83 '#' => "%23".to_owned(),
84 other => other.to_string(),
85 })
86 .collect()
87}
88
89/// A package URL, as the purl specification writes one.
90pub fn purl(ecosystem: Ecosystem, name: &str, version: &str) -> String {
91 let name = match ecosystem {
92 // A scope is a namespace: `@babel/core` is `%40babel/core`.
93 Ecosystem::Npm => purl_encode(name),
94 Ecosystem::PyPI => name.to_lowercase().replace('_', "-"),
95 _ => name.to_owned(),
96 };
97 format!("pkg:{}/{name}@{}", purl_type(ecosystem), purl_encode(version))
98}
99
100/// What a lockfile says beyond names and versions: the project's own
101/// dependencies (`None` when it does not say), those for development, and
102/// licenses by package.
103#[derive(Default)]
104struct Facts {
105 direct: Option<BTreeSet<String>>,
106 development: BTreeSet<(String, String)>,
107 direct_development: BTreeSet<String>,
108 licenses: BTreeMap<(String, String), String>,
109}
110
111/// Every package `text` resolves, with what it says about each.
112pub fn dependencies(lockfile: Lockfile, manifest: &str, text: &str) -> Vec<Dependency> {
113 let facts = match lockfile {
114 Lockfile::PackageLock => package_lock(text),
115 Lockfile::PnpmLock => pnpm_lock(text),
116 Lockfile::CargoLock => cargo_lock(text),
117 Lockfile::GoMod => go_mod(text),
118 Lockfile::Requirements => requirements(text),
119 Lockfile::YarnLock | Lockfile::GoSum | Lockfile::PoetryLock => Facts::default(),
120 };
121 let ecosystem = lockfile.ecosystem();
122 lockfile
123 .parse(text)
124 .into_iter()
125 .map(|package| {
126 let relationship = match &facts.direct {
127 Some(direct) if direct.contains(&ecosystem.normalize(&package.name)) => Relationship::Direct,
128 Some(_) => Relationship::Transitive,
129 None => Relationship::Unknown,
130 };
131 let key = (package.name.clone(), package.version.clone());
132 let development = facts.development.contains(&key)
133 || (relationship == Relationship::Direct && facts.direct_development.contains(&package.name));
134 Dependency {
135 license: facts.licenses.get(&key).cloned(),
136 manifest: manifest.to_owned(),
137 relationship,
138 development,
139 package,
140 }
141 })
142 .collect()
143}
144
145fn keys(value: Option<&Value>) -> impl Iterator<Item = String> + '_ {
146 value.and_then(Value::as_object).into_iter().flat_map(|object| object.keys().cloned())
147}
148
149/// `package-lock.json` v2 and v3: the root entry (`""`) names the project's
150/// dependencies; each package says `dev` and, from npm 7, its `license`.
151fn package_lock(text: &str) -> Facts {
152 let Ok(lock) = serde_json::from_str::<Value>(text) else {
153 return Facts::default();
154 };
155 let mut facts = Facts::default();
156 if let Some(packages) = lock.get("packages").and_then(Value::as_object) {
157 let mut direct = BTreeSet::new();
158 for (path, entry) in packages {
159 // The project and its workspaces: what they ask for is direct.
160 if !path.contains("node_modules/") {
161 for field in ["dependencies", "optionalDependencies", "peerDependencies"] {
162 direct.extend(keys(entry.get(field)));
163 }
164 for name in keys(entry.get("devDependencies")) {
165 facts.direct_development.insert(name.clone());
166 direct.insert(name);
167 }
168 continue;
169 }
170 let at = path.rfind("node_modules/").unwrap_or(0) + "node_modules/".len();
171 let name = entry.get("name").and_then(Value::as_str).unwrap_or(&path[at..]).to_owned();
172 let Some(version) = entry.get("version").and_then(Value::as_str) else { continue };
173 let key = (name, version.to_owned());
174 if entry.get("dev").and_then(Value::as_bool) == Some(true) {
175 facts.development.insert(key.clone());
176 }
177 let license = match entry.get("license") {
178 Some(Value::String(license)) => Some(license.clone()),
179 Some(Value::Object(object)) => object.get("type").and_then(Value::as_str).map(str::to_owned),
180 _ => None,
181 };
182 if let Some(license) = license.filter(|license| !license.trim().is_empty()) {
183 facts.licenses.insert(key, license);
184 }
185 }
186 facts.direct = Some(direct);
187 } else if let Some(dependencies) = lock.get("dependencies").and_then(Value::as_object) {
188 // v1 nests what each package needs under it; the top level is
189 // everything hoisted, which is not the same as direct.
190 for (name, entry) in dependencies {
191 if entry.get("dev").and_then(Value::as_bool) == Some(true)
192 && let Some(version) = entry.get("version").and_then(Value::as_str)
193 {
194 facts.development.insert((name.clone(), version.to_owned()));
195 }
196 }
197 }
198 facts
199}
200
201/// The name a pnpm importer line gives, unquoted: ` '@babel/core':`.
202fn yaml_key(line: &str) -> Option<String> {
203 let key = line.trim().strip_suffix(':').or_else(|| line.trim().split_once(": ").map(|(key, _)| key))?;
204 let key = key.trim().trim_matches(['\'', '"']);
205 (!key.is_empty()).then(|| key.to_owned())
206}
207
208fn indent(line: &str) -> usize {
209 line.len() - line.trim_start_matches(' ').len()
210}
211
212/// `pnpm-lock.yaml`: v6 and v9 list each importer's dependencies under
213/// `importers:`; v5 and single-project v6 at the top level.
214fn pnpm_lock(text: &str) -> Facts {
215 let mut direct = BTreeSet::new();
216 let mut development = BTreeSet::new();
217 let mut section = String::new();
218 // Under `importers`: the indentation of the current dependency list,
219 // and whether it is for development.
220 let mut list: Option<(usize, bool)> = None;
221 let mut found_any = false;
222 for line in text.lines() {
223 if line.trim().is_empty() || line.trim_start().starts_with('#') {
224 continue;
225 }
226 let depth = indent(line);
227 if depth == 0 {
228 section = line.trim_end_matches(':').trim().to_owned();
229 list = None;
230 continue;
231 }
232 match section.as_str() {
233 "dependencies" | "optionalDependencies" | "devDependencies" if depth == 2 => {
234 if let Some(name) = yaml_key(line) {
235 found_any = true;
236 if section == "devDependencies" {
237 development.insert(name.clone());
238 }
239 direct.insert(name);
240 }
241 }
242 "importers" => {
243 let field = line.trim().trim_end_matches(':');
244 if depth == 4 {
245 list = matches!(field, "dependencies" | "optionalDependencies" | "devDependencies")
246 .then_some((depth, field == "devDependencies"));
247 } else if let Some((at, dev)) = list
248 && depth == at + 2
249 && let Some(name) = yaml_key(line)
250 {
251 found_any = true;
252 if dev {
253 development.insert(name.clone());
254 }
255 direct.insert(name);
256 } else if depth <= 2 {
257 list = None;
258 }
259 }
260 _ => {}
261 }
262 }
263 Facts {
264 direct: found_any.then_some(direct),
265 direct_development: development,
266 ..Facts::default()
267 }
268}
269
270/// `Cargo.lock`: the project's own crates have no `source`, and their
271/// `dependencies` arrays name what they use directly.
272fn cargo_lock(text: &str) -> Facts {
273 let mut direct = BTreeSet::new();
274 let mut local = false;
275 let mut in_dependencies = false;
276 let mut pending: Vec<String> = Vec::new();
277 let flush = |local: bool, pending: &mut Vec<String>, direct: &mut BTreeSet<String>| {
278 if local {
279 direct.extend(pending.drain(..));
280 }
281 pending.clear();
282 };
283 for line in text.lines() {
284 let trimmed = line.trim();
285 if trimmed.starts_with('[') && !in_dependencies {
286 flush(local, &mut pending, &mut direct);
287 local = trimmed == "[[package]]";
288 continue;
289 }
290 if in_dependencies {
291 if trimmed.starts_with(']') {
292 in_dependencies = false;
293 continue;
294 }
295 // `"serde"`, `"serde 1.0.0"`, `"serde 1.0.0 (registry+…)"`.
296 if let Some(name) = trimmed.trim_end_matches(',').trim_matches('"').split_whitespace().next() {
297 pending.push(name.to_owned());
298 }
299 continue;
300 }
301 if let Some((key, value)) = trimmed.split_once('=') {
302 match key.trim() {
303 "source" => local = false,
304 "dependencies" => {
305 let value = value.trim();
306 if value.starts_with('[') && value.ends_with(']') {
307 for item in value.trim_matches(['[', ']']).split(',') {
308 if let Some(name) = item.trim().trim_matches('"').split_whitespace().next() {
309 pending.push(name.to_owned());
310 }
311 }
312 } else {
313 in_dependencies = true;
314 }
315 }
316 _ => {}
317 }
318 }
319 }
320 flush(local, &mut pending, &mut direct);
321 Facts { direct: Some(direct), ..Facts::default() }
322}
323
324/// `go.mod`: a requirement marked `// indirect` is transitive.
325fn go_mod(text: &str) -> Facts {
326 let mut direct = BTreeSet::new();
327 let mut block = false;
328 for raw in text.lines() {
329 let indirect = raw.contains("// indirect");
330 let line = raw.split("//").next().unwrap_or_default().trim();
331 if block {
332 if line == ")" {
333 block = false;
334 continue;
335 }
336 } else if line.starts_with("require (") || line == "require(" {
337 block = true;
338 continue;
339 }
340 let line = if block { line } else if let Some(rest) = line.strip_prefix("require ") { rest.trim() } else { continue };
341 if let Some(module) = line.split_whitespace().next()
342 && !indirect
343 {
344 direct.insert(module.to_owned());
345 }
346 }
347 Facts { direct: Some(direct), ..Facts::default() }
348}
349
350/// `requirements.txt`: everything listed is direct, unless pip-compile
351/// wrote it, whose `# via` notes say which came from the project's own
352/// requirements (`-r requirements.in`) and which from another package.
353fn requirements(text: &str) -> Facts {
354 let compiled = text.contains("# via");
355 let mut direct = BTreeSet::new();
356 let mut current: Option<String> = None;
357 let mut vias: Vec<String> = Vec::new();
358 let finish = |current: &mut Option<String>, vias: &mut Vec<String>, direct: &mut BTreeSet<String>| {
359 if let Some(name) = current.take()
360 && (!compiled || vias.iter().any(|via| via.starts_with("-r ") || via.starts_with("-c ")))
361 {
362 direct.insert(name);
363 }
364 vias.clear();
365 };
366 for line in text.lines() {
367 let trimmed = line.trim();
368 if let Some(via) = trimmed.strip_prefix("# via") {
369 let via = via.trim();
370 if !via.is_empty() {
371 vias.push(via.to_owned());
372 }
373 continue;
374 }
375 if trimmed.starts_with('#') && line.starts_with(" ") {
376 // pip-compile lists several sources a line each under `# via`.
377 vias.push(trimmed.trim_start_matches('#').trim().to_owned());
378 continue;
379 }
380 if trimmed.is_empty() || trimmed.starts_with('#') || trimmed.starts_with('-') {
381 continue;
382 }
383 finish(&mut current, &mut vias, &mut direct);
384 let name = trimmed.split(['=', '<', '>', '!', '~', '[', ';', ' ']).next().unwrap_or_default();
385 if !name.is_empty() {
386 current = Some(Ecosystem::PyPI.normalize(name));
387 }
388 }
389 finish(&mut current, &mut vias, &mut direct);
390 Facts { direct: Some(direct), ..Facts::default() }
391}
392
393#[cfg(test)]
394mod tests {
395 use super::*;
396
397 fn summary(lockfile: Lockfile, text: &str) -> Vec<String> {
398 dependencies(lockfile, "x", text)
399 .into_iter()
400 .map(|dep| {
401 format!(
402 "{}@{} {}{}{}",
403 dep.package.name,
404 dep.package.version,
405 dep.relationship.as_str(),
406 if dep.development { " dev" } else { "" },
407 dep.license.map(|license| format!(" {license}")).unwrap_or_default()
408 )
409 })
410 .collect()
411 }
412
413 #[test]
414 fn package_lock_says_direct_dev_and_license() {
415 let v3 = r#"{"lockfileVersion":3,"packages":{
416 "":{"name":"app","version":"1.0.0","dependencies":{"lodash":"^4"},"devDependencies":{"@babel/core":"^7"}},
417 "node_modules/lodash":{"version":"4.17.20","license":"MIT"},
418 "node_modules/@babel/core":{"version":"7.0.0","dev":true,"license":"MIT"},
419 "node_modules/@babel/core/node_modules/semver":{"version":"5.7.0","dev":true,"license":"ISC"}
420 }}"#;
421 assert_eq!(
422 summary(Lockfile::PackageLock, v3),
423 ["@babel/core@7.0.0 direct dev MIT", "lodash@4.17.20 direct MIT", "semver@5.7.0 transitive dev ISC"]
424 );
425 // v1 does not say what is direct.
426 let v1 = r#"{"lockfileVersion":1,"dependencies":{"minimist":{"version":"0.0.8","dev":true}}}"#;
427 assert_eq!(summary(Lockfile::PackageLock, v1), ["minimist@0.0.8 unknown dev"]);
428 }
429
430 #[test]
431 fn pnpm_importers_and_top_level_lists() {
432 let v9 = "lockfileVersion: '9.0'\n\nimporters:\n\n .:\n dependencies:\n lodash:\n specifier: ^4.17.0\n version: 4.17.20\n devDependencies:\n '@types/node':\n specifier: ^20\n version: 20.1.0\n\npackages:\n\n lodash@4.17.20:\n resolution: {}\n\n '@types/node@20.1.0':\n resolution: {}\n\n undici-types@5.26.5:\n resolution: {}\n";
433 assert_eq!(
434 summary(Lockfile::PnpmLock, v9),
435 ["@types/node@20.1.0 direct dev", "lodash@4.17.20 direct", "undici-types@5.26.5 transitive"]
436 );
437 let v5 = "lockfileVersion: 5.4\n\nspecifiers:\n lodash: ^4\n\ndependencies:\n lodash: 4.17.20\n\npackages:\n\n /lodash/4.17.20:\n resolution: {integrity: x}\n /ms/2.1.2:\n resolution: {integrity: y}\n";
438 assert_eq!(summary(Lockfile::PnpmLock, v5), ["lodash@4.17.20 direct", "ms@2.1.2 transitive"]);
439 }
440
441 #[test]
442 fn cargo_lock_direct_is_what_the_projects_crates_use() {
443 let lock = "version = 3\n\n[[package]]\nname = \"app\"\nversion = \"0.1.0\"\ndependencies = [\n \"serde\",\n \"time 0.1.43\",\n]\n\n[[package]]\nname = \"serde\"\nversion = \"1.0.0\"\nsource = \"registry+https://github.com/rust-lang/crates.io-index\"\ndependencies = [\n \"serde_derive\",\n]\n\n[[package]]\nname = \"serde_derive\"\nversion = \"1.0.0\"\nsource = \"registry+https://github.com/rust-lang/crates.io-index\"\n\n[[package]]\nname = \"time\"\nversion = \"0.1.43\"\nsource = \"registry+https://github.com/rust-lang/crates.io-index\"\n";
444 assert_eq!(
445 summary(Lockfile::CargoLock, lock),
446 ["serde@1.0.0 direct", "serde_derive@1.0.0 transitive", "time@0.1.43 direct"]
447 );
448 }
449
450 #[test]
451 fn go_mod_indirect_and_requirements_via() {
452 let module = "module example.com/app\n\nrequire golang.org/x/text v0.3.0\n\nrequire (\n\tgithub.com/gin-gonic/gin v1.6.0 // indirect\n\tgolang.org/x/net v0.7.0\n)\n";
453 assert_eq!(
454 summary(Lockfile::GoMod, module),
455 ["github.com/gin-gonic/gin@v1.6.0 transitive", "golang.org/x/net@v0.7.0 direct", "golang.org/x/text@v0.3.0 direct"]
456 );
457 let plain = "Django==3.2.0\nrequests==2.19.1\n";
458 assert_eq!(summary(Lockfile::Requirements, plain), ["django@3.2.0 direct", "requests@2.19.1 direct"]);
459 let compiled = "certifi==2024.2.2\n # via requests\nrequests==2.31.0\n # via -r requirements.in\nurllib3==2.2.1\n # via\n # -r requirements.in\n # requests\n";
460 assert_eq!(
461 summary(Lockfile::Requirements, compiled),
462 ["certifi@2024.2.2 transitive", "requests@2.31.0 direct", "urllib3@2.2.1 direct"]
463 );
464 // yarn.lock does not say.
465 let yarn = "lodash@^4.17.0:\n version \"4.17.20\"\n";
466 assert_eq!(summary(Lockfile::YarnLock, yarn), ["lodash@4.17.20 unknown"]);
467 }
468
469 #[test]
470 fn package_urls() {
471 assert_eq!(purl(Ecosystem::Npm, "@babel/core", "7.0.0"), "pkg:npm/%40babel/core@7.0.0");
472 assert_eq!(purl(Ecosystem::Cargo, "serde", "1.0.0"), "pkg:cargo/serde@1.0.0");
473 assert_eq!(purl(Ecosystem::Go, "golang.org/x/net", "v0.7.0"), "pkg:golang/golang.org/x/net@v0.7.0");
474 assert_eq!(purl(Ecosystem::PyPI, "Django_Rest", "3.2.0"), "pkg:pypi/django-rest@3.2.0");
475 }
476}