pubsat 0.1.0

Building blocks for SAT-based dependency resolvers: a node-semver-compatible range parser, an ecosystem-independent constraint vocabulary, and a backend-agnostic SAT problem/solver abstraction with a Varisat backend.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

//! End-to-end resolution wall clock on synthetic dep graphs of
//! varying size.
//!
//! The architecture doc cites 200–500 ms on real `express`-sized
//! graphs (~68 transitive deps). This bench builds a synthetic
//! graph of comparable shape and measures the full pipeline:
//! `build → encode → solve`. Bench sizes (10, 25, 50, 100
//! packages) bracket the typical workload.

use std::sync::Arc;

use criterion::{BenchmarkId, Criterion, Throughput, criterion_group, criterion_main};
use pubsat::builder::DependencyGraphBuilder;
use pubsat::registry::{MockRegistry, VersionMetadata};
use pubsat::resolver::DependencyResolver;
use pubsat::version::VersionSet;
use semver::Version;
use tokio::runtime::Runtime;

/// Build a synthetic registry of `n` packages where each package
/// has 3 versions and depends on a small chain of earlier
/// packages — a depth-3 cascade that exercises the recursive walk
/// and the SAT-with-preferences pipeline without being trivial.
fn build_synthetic_registry(n: usize) -> (Arc<MockRegistry>, VersionMetadata) {
    let mut registry = MockRegistry::new();
    let names: Vec<String> = (0..n).map(|i| format!("pkg_{:03}", i)).collect();

    // Each package has versions 1.0.0, 1.1.0, 2.0.0.
    let versions = ["1.0.0", "1.1.0", "2.0.0"];
    for name in &names {
        registry = registry.with_versions(name.clone(), &versions);
    }

    // Each pkg_i depends on pkg_{i-1}, pkg_{i-2}, pkg_{i-3} (mod n,
    // when index goes negative we just skip — pkg_0 has no deps).
    let caret_set: VersionSet = "^1.0.0".parse().unwrap();
    for i in 1..n {
        for &offset in &[1usize, 2, 3] {
            if i < offset {
                continue;
            }
            let parent = &names[i];
            let child = &names[i - offset];
            for v in &versions {
                registry =
                    registry.with_dependency(parent.clone(), v, child.clone(), caret_set.clone());
            }
        }
    }

    // Root depends on the last 5 packages — a realistic "my-app
    // pulls in N top-level deps" shape.
    let mut root = VersionMetadata::new("synthetic-root", Version::new(1, 0, 0));
    for name in names.iter().rev().take(5) {
        root.dependencies.insert(name.clone(), caret_set.clone());
    }

    (Arc::new(registry), root)
}

fn end_to_end_resolution(c: &mut Criterion) {
    let rt = Runtime::new().unwrap();
    let mut group = c.benchmark_group("resolver/end_to_end");

    for &n in &[10usize, 25, 50, 100] {
        group.throughput(Throughput::Elements(n as u64));
        group.bench_with_input(BenchmarkId::from_parameter(n), &n, |b, &n| {
            b.to_async(&rt).iter_batched(
                || build_synthetic_registry(n),
                |(registry, root)| async move {
                    let graph = DependencyGraphBuilder::new(registry.clone())
                        .build(root)
                        .await
                        .unwrap();
                    DependencyResolver::new(registry)
                        .resolve(graph)
                        .await
                        .unwrap()
                },
                criterion::BatchSize::SmallInput,
            );
        });
    }

    group.finish();
}

criterion_group!(benches, end_to_end_resolution);
criterion_main!(benches);