Debugging the dependency resolution (Tarjan's SCC algorithm)

pmeunier

Jun 15, 2025, 8:45 AM

5IT7CXFGK6HHEWB3D4T5GDV3FZ7I2U7UKXOVSD7RVYSI3GFGVRTAC

Dependencies

• [2] BDEVQIAU Handle cyclic Ubuntu dependencies
• [3] UWQB743K First working shell (with ocaml code)
• [4] ODUDDQRY Adding the OCaml interface
• [5] 7Q4257EP Formatting, cleanup and Rust 2021 compatibility

Change contents

• replacement in src/extract.rs at line 2
  [3.104]→[3.19628:19671](∅→∅),[3.17213]→[3.19628:19671](∅→∅),[3.19628]→[3.19628:19671](∅→∅)
  − use std::collections::{BTreeSet, HashMap};
  [3.104]

  [3.19671]
  + use std::collections::{BTreeSet, HashMap, HashSet};
• edit in src/extract.rs at line 60
  [2.948]

  [2.948]
  + debug!("initial deps: {:?}", seen.get(pkg.package).unwrap());
• replacement in src/extract.rs at line 63
  [2.1011]→[2.1011:1242](∅→∅)
  − deps: seen

  − .get(pkg.package)

  − .unwrap()

  − .0

  − .iter()

  − .map(|x| seen.get(x).unwrap().1)

  − .collect(),
  [2.1011]

  [2.1242]
  + deps: Vec::new(),
• edit in src/extract.rs at line 88
  [2.2103]

  [2.2103]
  + for v in vertices.iter_mut() {

  + v.deps = seen

  + .get(v.pkg.package)

  + .unwrap()

  + .0

  + .iter()

  + .map(|x| seen.get(x).unwrap().1)

  + .collect()

  + }

  +
• edit in src/extract.rs at line 104
  [3.20502]

  [2.2230]
  + let mut ld_paths = HashSet::new();
• edit in src/extract.rs at line 106
  [2.2259]

  [2.2259]
  + ld_paths.clear();
• edit in src/extract.rs at line 124
  [2.3089]

  [2.3089]
  +

  + // Find the extra ld paths to look for.

  + vertices[*v].add_ld_paths().unwrap();

  + ld_paths.extend(vertices[*v].ld_path.iter().cloned());

  + for dep in vertices[*v].deps.iter() {

  + for l in vertices[*dep].ld_path.iter() {

  + ld_paths.insert(l.clone());

  + }

  + }
• edit in src/extract.rs at line 134
  [2.3099]

  [3.21719]
  + for v in scc.iter() {

  + for l in ld_paths.iter().cloned() {

  + if vertices[*v].ld_path_h.insert(l.clone()) {

  + vertices[*v].ld_path.push(l.clone());

  + }

  + }

  + }

  + for v in scc.iter() {

  + // Find the libs in this package.

  + vertices[*v].find_libs();

  + }
• replacement in src/extract.rs at line 152
  [3.19091]→[2.3285:3286](∅→∅),[2.3286]→[3.19091:19125](∅→∅),[3.19091]→[3.19091:19125](∅→∅),[3.19125]→[2.3287:3360](∅→∅),[2.3360]→[3.19169:19176](∅→∅),[3.19169]→[3.19169:19176](∅→∅)
  −

  − Ok(Packages {

  − result,

  − paths: vertices.last().unwrap().files.iter().cloned().collect(),

  − })
  [3.19091]

  [2.3361]
  + let paths = vertices.last().unwrap().files.iter().cloned().collect();

  + debug!("paths = {:?}", paths);

  + debug!("result = {:?}", result);

  + Ok(Packages { result, paths })
• edit in src/extract.rs at line 163
  [2.3507]

  [2.3507]
  + #[derive(Debug)]
• replacement in src/extract.rs at line 166
  [2.3541]→[2.3541:3560](∅→∅)
  − wj: usize,
  [2.3541]

  [2.3560]
  + d: usize,
• replacement in src/extract.rs at line 170
  [2.3632]→[2.3632:3647](∅→∅)
  − wj: 0,
  [2.3632]

  [2.3647]
  + d: 0,
• edit in src/extract.rs at line 174
  [2.3711]

  [2.3711]
  + debug!(

  + "visiting {:?}: {:?} {:?} {:?}",

  + c, vertices[c.vi].pkg.package, vertices[c.vi].index, vertices[c.vi].lowlink

  + );
• replacement in src/extract.rs at line 186
  [2.3960]→[2.3960:4057](∅→∅)
  − while c.wj < vertices[c.vi].deps.len() {

  − let wi = vertices[c.vi].deps[c.wj];
  [2.3960]

  [2.4057]
  + if c.d > 0 {

  + // Returning from the recursive call.

  + let dep = vertices[c.vi].deps[c.d - 1];

  + vertices[c.vi].lowlink = vertices[c.vi].lowlink.min(vertices[dep].lowlink);

  + }

  + while c.d < vertices[c.vi].deps.len() {

  + let wi = vertices[c.vi].deps[c.d];

  + debug!("dep of {:?}: {:?} ({:?})", c.vi, wi, vertices[c.vi].deps);
• replacement in src/extract.rs at line 198
  [2.4251]→[2.4251:4278](∅→∅)
  − c.wj += 1;
  [2.4251]

  [2.4278]
  + c.d += 1;
• replacement in src/extract.rs at line 200
  [2.4299]→[2.4299:4326](∅→∅)
  − c.wj += 1;
  [2.4299]

  [2.4326]
  + c.d += 1;
• replacement in src/extract.rs at line 202
  [2.4362]→[2.4362:4416](∅→∅)
  − call_stack.push(C { vi: wi, wj: 0 });
  [2.4362]

  [2.4416]
  + call_stack.push(C { vi: wi, d: 0 });

  + // Recursive call.
• edit in src/extract.rs at line 209
  [2.4577]

  [2.4577]
  + debug!("new scc");
• edit in src/extract.rs at line 211
  [2.4623]

  [2.4623]
  + debug!("-> {:?} {:?}", p, vertices[p].pkg.package);
• edit in src/extract.rs at line 423
  [2.7194]→[3.27306:27349](∅→∅),[3.27306]→[3.27306:27349](∅→∅)
  − debug!("checking {:?}", path);
• edit in src/extract.rs at line 431
  [3.23170]

  [3.23170]
  + debug!("find_libs {:?}: adding {:?}", self.pkg.package, path);
• replacement in src/extract.rs at line 512
  [3.30057]→[2.7420:7552](∅→∅)
  − for dep in self

  − .deps_paths

  − .iter()

  − .chain(self.transitive_deps.iter().rev())

  − {
  [3.30057]

  [3.23865]
  + debug!("needed: {:?} -> {:?}", f, needed);

  +

  + for dep in self.transitive_deps.iter().rev() {
• replacement in src/extract.rs at line 523
  [3.24106]→[3.24106:24176](∅→∅)
  − is_needed |= tokio::fs::metadata(&dep).await.is_ok();
  [3.24106]

  [3.24176]
  + let exists = tokio::fs::metadata(&dep).await.is_ok();

  + if exists {

  + debug!("exists {:?}", dep);

  + }

  + is_needed |= exists;
• edit in src/extract.rs at line 538
  [3.30356]

  [3.30356]
  +

  + // Add potential local libs.

  + let mut last_added = None;

  + for (d, _) in find_files(self.downloaded.path.clone())? {

  + if last_added.as_deref() == d.parent() {

  + continue;

  + }

  + for n in needed.iter() {

  + if d.file_name().unwrap().to_str().unwrap() == n {

  + last_added = d.parent().map(|x| x.to_path_buf());

  + if !path.is_empty() {

  + path.push(':')

  + }

  + let suffix = d

  + .parent()

  + .unwrap()

  + .strip_prefix(&self.downloaded.path)

  + .unwrap();

  + path.push_str(

  + self.context_path

  + .as_ref()

  + .unwrap()

  + .join(suffix)

  + .to_str()

  + .unwrap(),

  + );

  + }

  + }

  + }

  +
• edit in src/extract.rs at line 597
  [2.8273]

  [2.8273]
  + debug!(

  + "dep: {:?} -> {:?} {:?}",

  + vertices[v].pkg.package, dep, vertices[*dep].pkg.package

  + );
• edit in src/extract.rs at line 606
  [3.31099]

  [2.8426]
  + debug!("transitive {:?}", vertices[*dep].transitive_deps.len());
• replacement in src/extract.rs at line 611
  [2.8619]→[2.8619:8668](∅→∅)
  − vertices[v].pkg.package, dep
  [2.8619]

  [2.8668]
  + vertices[v].pkg.package, d
• edit in src/extract.rs at line 631
  [2.9307]→[3.31341:31342](∅→∅),[3.31341]→[3.31341:31342](∅→∅),[3.31342]→[2.9308:9393](∅→∅)
  −

  − // Find the extra ld paths to look for.

  − vertices[v].add_ld_paths().unwrap();
• edit in src/extract.rs at line 633
  [2.9456]→[2.9456:9523](∅→∅)
  − // Find the libs in this package.

  − vertices[v].find_libs();