Mon 10 Mar 2025

Babel

KILL python pubgrub

Using Uv’s dependency provider.

This isn’t feasible at present, as Uv implements a custom resolver.

DONE cargo pubgrub

Got a cargo dependency provider working modified from a repository used to benchmark pubgrub-rs on solving the cargo repository.

(Root, ) -> (Cargo Bucket:serde@1.x.y, SemverPubgrub { norml: 1.0.219, pre: ∅ } )
(Cargo Bucket:serde@1.x.y, 1.0.219) -> (Cargo Bucket:serde_derive@1.x.y, SemverPubgrub { norml: >=1.0.219, <1.0.220, pre: ∅ } ), (Cargo Bucket:serde_derive@1.x.y/default=true, SemverPubgrub { norml: >=1.0.219, <1.0.220, pre: ∅ } )
(Cargo Bucket:serde_derive@1.x.y, 1.0.219) -> (Cargo Bucket:quote@1.x.y/proc-macro, SemverPubgrub { norml: >=1.0.35, <2.0.0, pre: ∅ } ), (Cargo Bucket:syn@2.x.y/parsing, SemverPubgrub { norml: >=2.0.81, <3.0.0, pre: ∅ } ), (Cargo Bucket:syn@2.x.y, SemverPubgrub { norml: >=2.0.81, <3.0.0, pre: ∅ } ), (Cargo Bucket:syn@2.x.y/derive, SemverPubgrub { norml: >=2.0.81, <3.0.0, pre: ∅ } ), (Cargo Bucket:syn@2.x.y/clone-impls, SemverPubgrub { norml: >=2.0.81, <3.0.0, pre: ∅ } ), (Cargo Bucket:quote@1.x.y, SemverPubgrub { norml: >=1.0.35, <2.0.0, pre: ∅ } ), (Cargo Bucket:proc-macro2@1.x.y, SemverPubgrub { norml: >=1.0.74, <2.0.0, pre: ∅ } ), (Cargo Bucket:proc-macro2@1.x.y/proc-macro, SemverPubgrub { norml: >=1.0.74, <2.0.0, pre: ∅ } ), (Cargo Bucket:syn@2.x.y/proc-macro, SemverPubgrub { norml: >=2.0.81, <3.0.0, pre: ∅ } ), (Cargo Bucket:syn@2.x.y/printing, SemverPubgrub { norml: >=2.0.81, <3.0.0, pre: ∅ } )
(Cargo Bucket:serde_derive@1.x.y/default=true, 1.0.219) -> (Cargo Bucket:serde_derive@1.x.y, SemverPubgrub { norml: 1.0.219, pre: ∅ } ), (Cargo Bucket:serde_derive@1.x.y/default, SemverPubgrub { norml: 1.0.219, pre: ∅ } )
(Cargo Bucket:quote@1.x.y/proc-macro, 1.0.40) -> (Cargo Bucket:quote@1.x.y, SemverPubgrub { norml: 1.0.40, pre: ∅ } ), (Cargo Bucket:proc-macro2@1.x.y/proc-macro, SemverPubgrub { norml: >=1.0.80, <2.0.0, pre: ∅ } )
(Cargo Bucket:syn@2.x.y/parsing, 2.0.100) -> (Cargo Bucket:syn@2.x.y, SemverPubgrub { norml: 2.0.100, pre: ∅ } )
(Cargo Bucket:syn@2.x.y, 2.0.100) -> (Cargo Bucket:proc-macro2@1.x.y, SemverPubgrub { norml: >=1.0.91, <2.0.0, pre: ∅ } ), (Cargo Bucket:unicode-ident@1.x.y, SemverPubgrub { norml: >=1.0.0, <2.0.0, pre: ∅ } ), (Cargo Bucket:unicode-ident@1.x.y/default=true, SemverPubgrub { norml: >=1.0.0, <2.0.0, pre: ∅ } )
(Cargo Bucket:syn@2.x.y/derive, 2.0.100) -> (Cargo Bucket:syn@2.x.y, SemverPubgrub { norml: 2.0.100, pre: ∅ } )
(Cargo Bucket:syn@2.x.y/clone-impls, 2.0.100) -> (Cargo Bucket:syn@2.x.y, SemverPubgrub { norml: 2.0.100, pre: ∅ } )
(Cargo Bucket:quote@1.x.y, 1.0.40) -> (Cargo Bucket:proc-macro2@1.x.y, SemverPubgrub { norml: >=1.0.80, <2.0.0, pre: ∅ } )
(Cargo Bucket:proc-macro2@1.x.y, 1.0.94) -> (Cargo Bucket:unicode-ident@1.x.y, SemverPubgrub { norml: >=1.0.0, <2.0.0, pre: ∅ } ), (Cargo Bucket:unicode-ident@1.x.y/default=true, SemverPubgrub { norml: >=1.0.0, <2.0.0, pre: ∅ } )
(Cargo Bucket:proc-macro2@1.x.y/proc-macro, 1.0.94) -> (Cargo Bucket:proc-macro2@1.x.y, SemverPubgrub { norml: 1.0.94, pre: ∅ } )
(Cargo Bucket:syn@2.x.y/proc-macro, 2.0.100) -> (Cargo Bucket:quote@1.x.y/proc-macro, SemverPubgrub { norml: >=1.0.35, <2.0.0, pre: ∅ } ), (Cargo Bucket:syn@2.x.y/dep:quote, SemverPubgrub { norml: 2.0.100, pre: ∅ } ), (Cargo Bucket:proc-macro2@1.x.y/proc-macro, SemverPubgrub { norml: >=1.0.91, <2.0.0, pre: ∅ } ), (Cargo Bucket:syn@2.x.y, SemverPubgrub { norml: 2.0.100, pre: ∅ } )
(Cargo Bucket:syn@2.x.y/printing, 2.0.100) -> (Cargo Bucket:syn@2.x.y, SemverPubgrub { norml: 2.0.100, pre: ∅ } ), (Cargo Bucket:syn@2.x.y/dep:quote, SemverPubgrub { norml: 2.0.100, pre: ∅ } )
(Cargo Bucket:serde_derive@1.x.y/default, 1.0.219) -> (Cargo Bucket:serde_derive@1.x.y, SemverPubgrub { norml: 1.0.219, pre: ∅ } )
(Cargo Bucket:unicode-ident@1.x.y, 1.0.18)
(Cargo Bucket:unicode-ident@1.x.y/default=true, 1.0.18) -> (Cargo Bucket:unicode-ident@1.x.y, SemverPubgrub { norml: 1.0.18, pre: ∅ } )
(Cargo Bucket:syn@2.x.y/dep:quote, 2.0.100) -> (Cargo Bucket:syn@2.x.y, SemverPubgrub { norml: 2.0.100, pre: ∅ } ), (Cargo Bucket:quote@1.x.y, SemverPubgrub { norml: >=1.0.35, <2.0.0, pre: ∅ } )

You’ll notice the concept of version ranges in this dependency provider has a ‘normal’ range, and a ‘pre’ range, so I had to add an abstract BabelVersionSet to interoperate with the other dependency providers.

At the moment this loads the whole index at once which takes a long time, so I need to figure out how to make pubgrub_cargo dynamically load packages.

Getting Claude code to attempt this failed quite spectacularly, so I guess my job’s safe (for now);

We’ve run into significant challenges with implementing on-demand loading for the Cargo Index. The core issue is that the API was designed around a pre-loaded data model where all references have the same lifetime as the Index object.

Our efforts to update the code to use on-demand loading led us to the following conclusions:

Lifetime issues: Dependencies loaded on-demand don’t live long enough to satisfy the lifetime requirements of the API, which expects references that live for the entire lifetime of the Index. Ownership complexity: Even when cloning data to avoid borrowing issues, we still run into problems with the DependencyProvider trait expecting references with specific lifetimes. Deep architectural dependencies: The design assumes references are valid throughout the library’s operation, making it difficult to use dynamically loaded data without changing core APIs.

Recommendation:

For now, we should document these findings and revert to the pre-loaded approach while planning a more comprehensive redesign of the API to better support on-demand loading. This would involve:

Redesigning the DependencyProvider trait to work with owned data rather than references Updating the Names and Package types to avoid lifetime parameters Creating a proper caching layer for dynamically loaded data

This is a valuable learning experience that highlights the challenges of retrofitting on-demand loading into a system designed around pre-loaded data with static lifetim

Redesigning pubgrub_cargo to use an owned data approach like pubgrub_opam would be a substantial undertaking. Here’s a breakdown of the work involved: Scope of Changes

Core Type Redesign (3-5 days) Remove lifetime parameters from Names, Dependency, Index, and other key structs Redesign these to be fully owned types that implement Clone Update method signatures throughout the codebase

DependencyProvider Implementation (2-3 days) Rewrite methods like get_versions, get_version, and get_dependencies to return owned data Handle on-demand loading with proper caching

Package Resolution Logic (3-5 days) Modify pubgrub integration to work with owned data Update logic in from_dep, check_cycles, etc. to work without lifetime references

Testing & Debugging (3-5 days) Fix all the test cases that would break Debug subtle issues with different data ownership patterns Ensure performance remains acceptable

Challenges

Deep Architectural Change: The lifetime parameters are embedded deeply in the API, affecting almost every function. Interface Consistency: Need to ensure the redesign doesn’t break clients of the library. Performance Tradeoffs: Switching to owned data means more cloning, which could impact performance.

Total Estimate

A skilled Rust developer with good knowledge of the codebase would likely need 2-3 weeks of focused work to complete this redesign properly. The work would include refactoring, testing, debugging, and performance optimization.

If you just need a minimal working solution for now, reverting to the preloaded approach with selective loading of common packages might be a better near-term solution while planning the larger redesign.

The AI (and myself) both have a lot of issues with Rust lifetimes, and I really don’t care about optimising anything at this point. I miss OCaml’s garbage collector and am tempted to implemnt the Pubgrub algorithm in Oxidised OCaml.

TODO forking resolving for portable lockfiles

See Uv’s resolver.

Evaluation

  • stunt 1: cross-ecosystem solving
    • system dependency solving
      • debian and alpine
    • ocaml polars
  • stunt 2: portable lock files
    • portability metric
    • semantics from formalism
    • look at what uv does
    • add to table 1
  • stunt 3: cross-compilation
    • solving architectures

Providing packages

  • docker?
  • Nix?
  • namespaces?