3 Mar 2025

Previous: 25 Feb 2025 Next: 10 Mar 2025
  1. Babel

    1. A Debian encoding in PubGrub

      1. X provides with virtual packages

        here

    2. X cross ecosystem resolutions between opam and debian

      Done in babel.

      Some examples follow.

      1. conf-gmp

        #[test]
        fn test_conf_gmp_variables() -> Result<(), Box<dyn Error>> {
            let root = OpamPackage::Root(vec![
                (
                    OpamPackage::Base("conf-gmp".to_string()),
                    Range::singleton(OpamVersion("4".to_string())),
                ),
                (
                    OpamPackage::Var("os-family".to_string()),
                    Range::singleton(OpamVersion("debian".to_string())),
                ),
                (
                    OpamPackage::Var("os-distribution".to_string()),
                    Range::singleton(OpamVersion("debian".to_string())),
                ),
            ]);
            solve_repo(
                BabelPackage::Opam(root),
                BabelVersion::Opam(OpamVersion("".to_string())),
                "../pubgrub_opam/opam-repository/packages",
                "../pubgrub_debian/repositories/buster/Packages",
            )?;
            Ok(())
        }
        
        Solution Set:
                Debian  (libgmp10, 2:6.1.2+dfsg-4+deb10u1)
                Opam    os-family = debian
                Debian  (libc6, 2.28-10+deb10u1)
                Debian  (libgcc1, 1:8.3.0-6)
                Opam    os-distribution = debian
                Opam    os = linux
                Debian  (libstdc++6, 8.3.0-6)
                Debian  (libgmpxx4ldbl, 2:6.1.2+dfsg-4+deb10u1)
                Debian  (gcc-8-base, 8.3.0-6)
                Opam    (conf-gmp, 4)
                Debian  (libgmp-dev, 2:6.1.2+dfsg-4+deb10u1)
        
        Resolved Dependency Graph:
                (conf-gmp, 4) -> (Opam `os-distribution`, debian), (Opam `os-family`, debian), (Opam `os`, linux), (libgmp-dev, 2:6.1.2+dfsg-4+deb10u1)
                (gcc-8-base, 8.3.0-6)
                (libc6, 2.28-10+deb10u1) -> (libgcc1, 1:8.3.0-6)
                (libgcc1, 1:8.3.0-6) -> (gcc-8-base, 8.3.0-6), (libc6, 2.28-10+deb10u1)
                (libgmp-dev, 2:6.1.2+dfsg-4+deb10u1) -> (libgmp10, 2:6.1.2+dfsg-4+deb10u1), (libgmpxx4ldbl, 2:6.1.2+dfsg-4+deb10u1)
                (libgmp10, 2:6.1.2+dfsg-4+deb10u1) -> (libc6, 2.28-10+deb10u1)
                (libgmpxx4ldbl, 2:6.1.2+dfsg-4+deb10u1) -> (libc6, 2.28-10+deb10u1), (libgcc1, 1:8.3.0-6), (libgmp10, 2:6.1.2+dfsg-4+deb10u1), (libstdc++6, 8.3.0-6)
                (libstdc++6, 8.3.0-6) -> (gcc-8-base, 8.3.0-6), (libc6, 2.28-10+deb10u1), (libgcc1, 1:8.3.0-6)
        
      2. ocluster

        let root = OpamPackage::Root(vec![
            (
                OpamPackage::Base("ocluster".to_string()),
                Range::singleton(OpamVersion("0.3.0".to_string())),
            ),
            (
                OpamPackage::Var("os-family".to_string()),
                Range::singleton(OpamVersion("debian".to_string())),
            ),
            (
                OpamPackage::Var("os-distribution".to_string()),
                Range::singleton(OpamVersion("debian".to_string())),
            ),
        ]);
        solve_repo(
            BabelPackage::Opam(root),
            BabelVersion::Opam(OpamVersion("".to_string())),
            "../pubgrub_opam/opam-repository/packages",
            "../pubgrub_debian/repositories/buster/Packages",
        )?;
        Ok(())
        
        Solution Set:
                Opam    (ppx_deriving, 6.0.3)
                Opam    (stringext, 1.6.0)
                Debian  (libgcc1, 1:8.3.0-6)
                Opam    (mirage-crypto-ec, 0.11.3)
                Opam    (conduit-lwt-unix, 7.1.0)
                Opam    (bigstringaf, 0.10.0)
                Opam    (base-bytes, base)
                Opam    (angstrom, 0.16.1)
                Opam    (cstruct-lwt, 6.2.0)
                Opam    (sha, 1.15.4)
                Opam    (ppx_here, v0.17.0)
                Debian  (gcc-8-base, 8.3.0-6)
                Opam    (tls-mirage, 0.17.5)
                Opam    (conf-gmp, 4)
                Opam    (ocaml-compiler, 5.3)
                Opam    os-family = debian
                Opam    (ppx_inline_test, v0.17.0)
                Opam    (domain-name, 0.4.0)
                Opam    (extunix, 0.4.3)
                Opam    (eqaf, 0.9)
                Debian  (libstdc++6, 8.3.0-6)
                Opam    (mirage-crypto-rng, 0.11.3)
                Opam    opam-version = 2.1.0
                Opam    (ppx_base, v0.17.0)
                Opam    (yojson, 2.2.2)
                Opam    (ppx_expect, v0.17.2)
                Opam    (ocaml-variants, 5.3.1+trunk)
                Opam    (duration, 0.2.1)
                Opam    (ca-certs, 0.2.3)
                Opam    (pbkdf, 1.2.0)
                Opam    (zarith, 1.13)
                Opam    (prometheus, 1.2)
                Opam    (obuilder, 0.6.0)
                Opam    (psq, 0.2.1)
                Opam    (result, 1.5)
                Opam    (hmap, 0.8.1)
                Opam    (system-mingw, 1)
                Opam    (asetmap, 0.8.1)
                Opam    (cstruct, 6.2.0)
                Opam    (conf-mingw-w64-gcc-i686, 1)
                Opam    (ocplib-endian, 1.2)
                Opam    (cohttp-lwt, 6.0.0)
                Opam    (ipaddr-sexp, 5.6.0)
                Opam    (ocaml-env-mingw32, 1)
                Opam    (ocluster, 0.3.0)
                Opam    (ocaml, 5.3.1)
                Opam    (dune, 3.17.2)
                Opam    (base-unix, base)
                Opam    (magic-mime, 1.3.1)
                Debian  (libgmp-dev, 2:6.1.2+dfsg-4+deb10u1)
                Opam    (x509, 0.16.5)
                Opam    (fpath, 0.7.3)
                Opam    (fmt, 0.9.0)
                Opam    (ppxlib_jane, v0.17.2)
                Opam    (eio, 1.2)
                Opam    (optint, 0.3.0)
                Opam    (jst-config, v0.17.0)
                Opam    (re, 1.12.0)
                Opam    (csexp, 1.5.2)
                Opam    (base-bigarray, base)
                Debian  (libc6, 2.28-10+deb10u1)
                Opam    (sexplib0, v0.17.0)
                Opam    post = false
                Opam    (stdio, v0.17.0)
                Opam    (ppx_hash, v0.17.0)
                Opam    (ppx_cold, v0.17.0)
                Opam    (thread-table, 1.0.0)
                Opam    (uri, 4.4.0)
                Opam    (parsexp, v0.17.0)
                Opam    (base, v0.17.1)
                Opam    (conduit-lwt, 7.1.0)
                Opam    (cmdliner, 1.3.0)
                Opam    (mirage-crypto, 0.11.3)
                Opam    (sexplib, v0.17.0)
                Opam    (mtime, 2.1.0)
                Opam    (ppx_sexp_conv, v0.17.0)
                Opam    (mirage-flow, 5.0.0)
                Opam    (lwt-dllist, 1.0.1)
                Opam    os-distribution = debian
                Opam    (ocaml_intrinsics_kernel, v0.17.1)
                Opam    os = linux
                Opam    build = false
                Debian  (libgmpxx4ldbl, 2:6.1.2+dfsg-4+deb10u1)
                Opam    (capnp-rpc-lwt, 2.0)
                Opam    (ppx_compare, v0.17.0)
                Opam    (base-threads, base)
                Opam    (logs, 0.7.0)
                Opam    (stdlib-shims, 0.3.0)
                Opam    (dune-configurator, 3.17.2)
                Opam    (ipaddr, 5.6.0)
                Opam    (res, 5.0.2)
                Opam    (capnp-rpc-net, 1.2.3)
                Opam    (tar-unix, 2.6.0)
                Opam    (ppx_assert, v0.17.0)
                Opam    (mirage-kv, 6.1.1)
                Debian  (libev4, 1:4.25-1)
                Opam    with-dev-setup = false
                Opam    (lwt, 5.9.0)
                Opam    (ppx_globalize, v0.17.0)
                Opam    (mirage-crypto-pk, 0.11.3)
                Opam    (rresult, 0.7.0)
                Opam    (conf-libev, 4-12)
                Opam    (capnp, 3.6.0)
                Opam    (time_now, v0.17.0)
                Opam    (domain-local-await, 1.0.1)
                Opam    (stdint, 0.7.2)
                Debian  (libgmp10, 2:6.1.2+dfsg-4+deb10u1)
                Opam    (digestif, 1.2.0)
                Opam    with-test = false
                Opam    (lwt_eio, 0.5.1)
                Opam    (sqlite3, 5.3.0)
                Opam    (asn1-combinators, 0.2.6)
                Opam    with-doc = false
                Opam    (dune-build-info, 3.17.2)
                Opam    (num, 1.5-1)
                Opam    (prometheus-app, 1.2)
                Opam    dev = false
                Opam    (capnp-rpc-unix, 1.2.4)
                Opam    (ppx_derivers, 1.2.1)
                Opam    (gmap, 0.3.0)
                Opam    (astring, 0.8.5)
                Opam    (bos, 0.2.1)
                Opam    (hkdf, 1.0.4)
                Opam    (mirage-crypto-rng-lwt, 1.2.0)
                Opam    (mirage-clock, 4.2.0)
                Opam    (ocaml-compiler-libs, v0.17.0)
                Opam    (ptime, 1.2.0)
                Opam    arch = x86_64
                Opam    (ocaml-config, 3)
                Opam    (jane-street-headers, v0.17.0)
                Opam    (ppxlib, 0.35.0)
                Opam    (seq, base)
                Opam    version = false
                Opam    (cohttp-lwt-unix, 6.0.0)
                Opam    (base64, 3.5.1)
                Opam    (ppx_enumerate, v0.17.0)
                Opam    (ppx_optcomp, v0.17.0)
                Opam    (ocamlfind, 1.9.8)
                Opam    (tls, 0.17.5)
                Debian  (libev-dev, 1:4.25-1)
        
    3. X An Alpine encoding in PubGrub

      $ apk dot openssh-server
      digraph "apkindex" {
        rankdir=LR;
        node [shape=box];
        "libcrypto3-3.3.3-r0" -> "musl-1.2.5-r1"[arrowhead=inv,label="so:libc.musl-x86_64.so.1",];
        "openssh-keygen-9.7_p1-r5" -> "libcrypto3-3.3.3-r0"[];
        "openssh-keygen-9.7_p1-r5" -> "musl-1.2.5-r1"[arrowhead=inv,label="so:libc.musl-x86_64.so.1",];
        "openssh-keygen-9.7_p1-r5" -> "libcrypto3-3.3.3-r0"[arrowhead=inv,label="so:libcrypto.so.3",];
        "openssh-server-9.7_p1-r5" -> "openssh-keygen-9.7_p1-r5"[];
        "openssh-server-9.7_p1-r5" -> "openssh-server-common-9.7_p1-r5"[];
        "openssh-server-9.7_p1-r5" -> "musl-1.2.5-r1"[arrowhead=inv,label="so:libc.musl-x86_64.so.1",];
        "openssh-server-9.7_p1-r5" -> "libcrypto3-3.3.3-r0"[arrowhead=inv,label="so:libcrypto.so.3",];
        "zlib-1.3.1-r1" -> "musl-1.2.5-r1"[arrowhead=inv,label="so:libc.musl-x86_64.so.1",];
        "openssh-server-9.7_p1-r5" -> "zlib-1.3.1-r1"[arrowhead=inv,label="so:libz.so.1",];
      }
      
      (/bin/sh, yash-binsh) -> (yash-binsh, 2.57-r0)
      (libcrypto3, 3.3.3-r0) -> (so:libc.musl-x86_64.so.1, musl)
      (libncursesw, 6.5_p20241006-r3) -> (ncurses-terminfo-base, 6.5_p20241006-r3), (so:libc.musl-x86_64.so.1, musl)
      (musl, 1.2.5-r9)
      (ncurses-terminfo-base, 6.5_p20241006-r3)
      (openssh-keygen, 9.9_p2-r0) -> (libcrypto3, 3.3.3-r0), (so:libc.musl-x86_64.so.1, musl), (so:libcrypto.so.3, libcrypto3)
      (openssh-server, 9.9_p2-r0) -> (/bin/sh, yash-binsh), (openssh-keygen, 9.9_p2-r0), (openssh-server-common, 9.9_p2-r0), (so:libc.musl-x86_64.so.1, musl), (so:libcrypto.so.3, libcrypto3), (so:libz.so.1, zlib)
      (openssh-server-common, 9.9_p2-r0)
      (so:libc.musl-x86_64.so.1, musl) -> (musl, 1.2.5-r9)
      (so:libcrypto.so.3, libcrypto3) -> (libcrypto3, 3.3.3-r0)
      (so:libncursesw.so.6, libncursesw) -> (libncursesw, 6.5_p20241006-r3)
      (so:libz.so.1, zlib) -> (zlib, 1.3.1-r2)
      (yash, 2.57-r0) -> (/bin/sh, yash-binsh), (so:libc.musl-x86_64.so.1, musl), (so:libncursesw.so.6, libncursesw)
      (yash-binsh, 2.57-r0) -> (yash, 2.57-r0)
      (zlib, 1.3.1-r2) -> (so:libc.musl-x86_64.so.1, musl)
      

      We could similarly prune out virtual packages.

    4. O read up on answer set programming

      https://pubgrub-rs-guide.pages.dev/internals/intro is a good starting point

    5. O benchmark pubgrub against zero install

    6. O paper resubmission

      3 stunts:

      • stunt 1: cross-ecosystem solving
        • debian and alpine MVP
      • stunt 2: portable lock files
        • portability metric
        • semantics from formalism
        • look at what uv does
        • add to table 1
      • stunt 3: gpu package
        • filesystems
        • hetrogenous hardware
        • intel amd
    7. O think about uses of this graph other than solving

      1. security vunrabilities - USENIX security

      2. local vector db of internet scale packages managers

  2. paper plans

    1. Babel to SPLASH

    2. Shark to SOSP

    3. Eilean to HotNets idea

    4. Spatial Name System sensor networks to SIGCOMM idea

    5. Agentic systems to use Babel to NeurIPS idea

  3. meeting

    1. O consider opam env requirement for providing packages once solved

    2. O how to generate depexts for everything

      • e.g. tries to link to libssl
      • run build log through LLM
      • or instrument the compiler
        • assuming a successful link
        • or see where it fails
        • cargo and ocaml
    3. evaluation

      1. ocaml-polars

      2. portable lock files

    4. artefact: selected a subset of ecosystems in this eval for you to try

    5. contributions: cross-ecosystem, tooling, partial evaluation