pmeunier/elpe - Change 5IT7CXFGK6HHEWB3D4T5GDV3FZ7I2U7UKXOVSD7RVYSI3GFGVRTAC

Debugging the dependency resolution (Tarjan's SCC algorithm)

Created by pmeunier on June 15, 2025

5IT7CXFGK6HHEWB3D4T5GDV3FZ7I2U7UKXOVSD7RVYSI3GFGVRTAC

Dependencies

In channels

main

Change contents

Replacement in src/extract.rs at line 2 [4.19587]
∅:D[3.104] → [4.19628:19671]
∅:D[5.17213] → [4.19628:19671]
B:BD[4.19628] → [4.19628:19671]
```
use std::collections::{BTreeSet, HashMap};
```
[3.104]
[4.19671]
```
use std::collections::{BTreeSet, HashMap, HashSet};
```

Insertion in src/extract.rs at line 60 [4.19587]

[2.948]

            debug!("initial deps: {:?}", seen.get(pkg.package).unwrap());

Replacement in src/extract.rs at line 63 [4.19587]

B:BD[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(),

Insertion in src/extract.rs at line 88 [4.19587]

[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()
    }

Insertion in src/extract.rs at line 104 [4.19587]
[4.20502]
[2.2230]
```
    let mut ld_paths = HashSet::new();
```
Insertion in src/extract.rs at line 106 [4.19587]
[2.2259]
[2.2259]
```
        ld_paths.clear();
```

Insertion in src/extract.rs at line 124 [4.19587]

[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());
                }
            }

Insertion in src/extract.rs at line 134 [4.19587]

[2.3099]

[4.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 [4.19587]

B:BD[5.19091] → [2.3285:3286]

∅:D[2.3286] → [5.19091:19125]

B:BD[5.19091] → [5.19091:19125]

B:BD[5.19125] → [2.3287:3360]

∅:D[2.3360] → [5.19169:19176]

B:BD[5.19169] → [5.19169:19176]


    Ok(Packages {
        result,
        paths: vertices.last().unwrap().files.iter().cloned().collect(),
    })

[5.19091]

[2.3361]

    let paths = vertices.last().unwrap().files.iter().cloned().collect();
    debug!("paths = {:?}", paths);
    debug!("result = {:?}", result);
    Ok(Packages { result, paths })

Insertion in src/extract.rs at line 163 [4.19587]
[2.3507]
[2.3507]
```
    #[derive(Debug)]
```
Replacement in src/extract.rs at line 166 [4.19587]
B:BD[2.3541] → [2.3541:3560]
```
        wj: usize,
```
[2.3541]
[2.3560]
```
        d: usize,
```
Replacement in src/extract.rs at line 170 [4.19587]
B:BD[2.3632] → [2.3632:3647]
```
        wj: 0,
```
[2.3632]
[2.3647]
```
        d: 0,
```

Insertion in src/extract.rs at line 174 [4.19587]

[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 [4.19587]

B:BD[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 [4.19587]
B:BD[2.4251] → [2.4251:4278]
```
                c.wj += 1;
```
[2.4251]
[2.4278]
```
                c.d += 1;
```
Replacement in src/extract.rs at line 200 [4.19587]
B:BD[2.4299] → [2.4299:4326]
```
                c.wj += 1;
```
[2.4299]
[2.4326]
```
                c.d += 1;
```

Replacement in src/extract.rs at line 202 [4.19587]

B:BD[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.

Insertion in src/extract.rs at line 209 [4.19587]
[2.4577]
[2.4577]
```
            debug!("new scc");
```

Insertion in src/extract.rs at line 211 [4.19587]

[2.4623]

                debug!("-> {:?} {:?}", p, vertices[p].pkg.package);

Deletion in src/extract.rs at line 423 [4.19587]
∅:D[2.7194] → [4.27306:27349]
B:BD[4.27306] → [4.27306:27349]
```
            debug!("checking {:?}", path);
```

Insertion in src/extract.rs at line 431 [4.19587]

[5.23170]

                    debug!("find_libs {:?}: adding {:?}", self.pkg.package, path);

Replacement in src/extract.rs at line 512 [4.19587]

B:BD[4.30057] → [2.7420:7552]

        for dep in self
            .deps_paths
            .iter()
            .chain(self.transitive_deps.iter().rev())
        {

[4.30057]

[5.23865]

        debug!("needed: {:?} -> {:?}", f, needed);
        for dep in self.transitive_deps.iter().rev() {

Replacement in src/extract.rs at line 523 [4.19587]

B:BD[5.24106] → [5.24106:24176]

                is_needed |= tokio::fs::metadata(&dep).await.is_ok();

[5.24106]

[5.24176]

                let exists = tokio::fs::metadata(&dep).await.is_ok();
                if exists {
                    debug!("exists {:?}", dep);
                }
                is_needed |= exists;

Insertion in src/extract.rs at line 538 [4.19587]

[4.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(),
                    );
                }
            }
        }

Insertion in src/extract.rs at line 597 [4.19587]

[2.8273]

        debug!(
            "dep: {:?} -> {:?} {:?}",
            vertices[v].pkg.package, dep, vertices[*dep].pkg.package
        );

Insertion in src/extract.rs at line 606 [4.19587]

[4.31099]

[2.8426]

        debug!("transitive {:?}", vertices[*dep].transitive_deps.len());

Replacement in src/extract.rs at line 611 [4.19587]

B:BD[2.8619] → [2.8619:8668]

                    vertices[v].pkg.package, dep

[2.8619]

[2.8668]

                    vertices[v].pkg.package, d

Deletion in src/extract.rs at line 631 [4.19587]
∅:D[2.9307] → [4.31341:31342]
B:BD[4.31341] → [4.31341:31342]
B:BD[4.31342] → [2.9308:9393]
```
    // Find the extra ld paths to look for.
    vertices[v].add_ld_paths().unwrap();
```
Deletion in src/extract.rs at line 633 [4.19587]
B:BD[2.9456] → [2.9456:9523]
```
    // Find the libs in this package.
    vertices[v].find_libs();
```

Debugging the dependency resolution (Tarjan's SCC algorithm)

Dependencies

In channels

Change contents

Replacement in src/extract.rs at line 2 [4.19587]

Insertion in src/extract.rs at line 60 [4.19587]

Replacement in src/extract.rs at line 63 [4.19587]

Insertion in src/extract.rs at line 88 [4.19587]

Insertion in src/extract.rs at line 104 [4.19587]

Insertion in src/extract.rs at line 106 [4.19587]

Insertion in src/extract.rs at line 124 [4.19587]

Insertion in src/extract.rs at line 134 [4.19587]

Replacement in src/extract.rs at line 152 [4.19587]

Insertion in src/extract.rs at line 163 [4.19587]

Replacement in src/extract.rs at line 166 [4.19587]

Replacement in src/extract.rs at line 170 [4.19587]

Insertion in src/extract.rs at line 174 [4.19587]

Replacement in src/extract.rs at line 186 [4.19587]

Replacement in src/extract.rs at line 198 [4.19587]

Replacement in src/extract.rs at line 200 [4.19587]

Replacement in src/extract.rs at line 202 [4.19587]

Insertion in src/extract.rs at line 209 [4.19587]