2 Sep 2024

Previous: 26 Aug 2024 Next: 9 Sep 2024

Tue
1. Try dumping the SAT graph to see how big we make it
2. hmm, magic trace traces are empty
3. Spent some trying to understand the SAT solving
Wed
```
sat: TRYING: not(cargo-quote.1.0.32)
sat: enqueue: not(cargo-quote.1.0.32) (considering)
sat: TRYING: not(cargo-quote.1.0.33)
sat: enqueue: not(cargo-quote.1.0.33) (considering)
sat: TRYING: not(cargo-quote.1.0.34)
sat: enqueue: not(cargo-quote.1.0.34) (considering)
sat: TRYING: not(cargo-quote.1.0.35)
sat: enqueue: not(cargo-quote.1.0.35) (considering)
sat: TRYING: not(cargo-quote.1.0.36)
sat: enqueue: not(cargo-quote.1.0.36) (considering)
sat: TRYING: not(cargo-quote.1.0.37)
sat: enqueue: not(cargo-quote.1.0.37) (considering)
sat: TRYING: not()
sat: enqueue: not() (considering)
sat: enqueue: not(cargo-wasm-bindgen.0.2.66) (<some: not(cargo-wasm-bindgen.0.2.66), , cargo-wasm-bindgen-macro.0.2.66>)
sat: enqueue: not(cargo-wasm-bindgen.0.2.66) (<some: not(cargo-wasm-bindgen.0.2.66), cargo-wasm-bindgen.0.2.66>)
sat: TRYING: not()
sat: enqueue: not() (considering)
sat: TRYING: not(cargo-cfg-if.0.1.9)
sat: enqueue: not(cargo-cfg-if.0.1.9) (considering)
```
we’re trying a whole bunch of nots… I think our problems might stem from the structure of the SAT problem rather than it’s size
```
time dune exec -- bin/main.exe --repo /dev/shm/opam-giga-repository/packages cargo-sauron-core.0.57.0
hooooo
ha
5116
flush
```
```
time dune exec -- bin/main.exe --repo /dev/shm/opam-giga-repository/packages cargo-sauron-core.0.57.0
hooooo
ha
114649
flush
^C
```
that is a lot bigger a SAT problem… how do we build the sat problem from roles and implementations? maybe we could do an optimisation if a role only has one implementation?

ah! Sat.at_most_one adds a clause

process_dep adds a clause for dependencies for every implementation
```
let implies problem ?reason first rest = at_least_one problem ?reason ((neg first) :: rest)
```
so basically we’re creating separate dependency info for every implementation now

okay, we’re down to 110816 with removing the implementation clause when there’s only one implementation
- question: does this break anything?
okay, we get to `cargo-thiserror.1.0.0` on line 219 with the o.g. solver compared to >20k with the modified solver

(there are many software deployment methodologies out there but we can solve across them)
```
(* A clause with only a single literal is represented
   as an assignment rather than as a clause. *)
```
okay, so clauses stored in literal watch lists? I don’t think it’ll be as easy to print this as I thought

change at_most_one to at_least_one? no, we might return multiple versions

what if we just return the upper bound of every dependency???

that did it!

tomorrow: Next up is supporting both of these in one dependency tree, which might require adding a new flag to the cargo opam files I mean if we’re solving dependencies that cross package ecosystem lines, e.g. an opam package depending on a cargo package, or a cargo package depending on a debian package. We would want to allow multiple versions for the cargo package, but not the opam or debiain packages. So if I have some flag associated with each package I can choose whether to represent them in a way that allows multiple versions (or not)

Thu

Can't find all required versions.
Selected: opam-angstrom.0.16.0 opam-base.v0.17.1 opam-base-bigarray.base
          opam-base-domains.base opam-base-nnp.base opam-base-threads.base
          opam-base-unix.base opam-base64.3.5.1 opam-bigstringaf.0.10.0
          opam-csexp.1.5.2 opam-dune.3.16.0 opam-dune-configurator.3.16.0
          opam-host-arch-x86_64.1 opam-jsonm.1.0.2 opam-ocaml.4.14.3
          opam-ocaml.5.2.0 opam-ocaml.5.2.1 opam-ocaml.5.4.0
          opam-ocaml-base-compiler.5.2.0 opam-ocaml-compiler-libs.v0.17.0
          opam-ocaml-config.3 opam-ocaml-option-bytecode-only.1
          opam-ocaml-options-vanilla.1 opam-ocaml-syntax-shims.1.0.0
          opam-ocaml_intrinsics_kernel.v0.17.1 opam-ocamlbuild.0.15.0
          opam-ocamlfind.1.9.6 opam-ppx_derivers.1.2.1
          opam-ppx_sexp_conv.v0.17.0 opam-ppxlib.0.33.0
          opam-ppxlib_jane.v0.17.0 opam-re.1.11.0 opam-seq.base
          opam-sexplib0.v0.17.0 opam-stdlib-shims.0.3.0 opam-stringext.1.6.0
          opam-topkg.1.0.7 opam-uri.4.4.0 opam-uri-sexp.4.4.0 opam-uutf.1.0.3
          opam-cohttp.5.3.1 opam-cohttp.5.3.1 opam-ocaml.4.14.3
          opam-ocaml-base-compiler.5.2.0 opam-ocaml-option-bytecode-only.1
          opam-ocaml-base-compiler.5.2.0 opam-ocaml.5.4.0
          opam-base-domains.base opam-ocaml-base-compiler.5.2.0
          opam-ocaml.5.4.0
- opam-cohttp.5.3.1 -> opam-cohttp.5.3.1
    User requested = 5.3.1
- opam-ocaml-variants.4.14.3+trunk -> (problem)
    Rejected candidates:
      opam-ocaml-variants.4.14.3+trunk: In same conflict class (ocaml-core-compiler) as opam-ocaml-base-compiler.5.2.0
      opam-ocaml-variants.5.2.0+trunk: Availability condition not satisfied
      opam-ocaml-variants.5.1.1+trunk: Availability condition not satisfied
      opam-ocaml-variants.5.1.0+trunk: Availability condition not satisfied
      opam-ocaml-variants.5.0.0+trunk: Availability condition not satisfied
      ...
- opam-ocaml-variants.5.2.1+trunk -> (problem)
    Rejected candidates:
      opam-ocaml-variants.5.2.1+trunk: In same conflict class (ocaml-core-compiler) as opam-ocaml-base-compiler.5.2.0
      opam-ocaml-variants.5.2.0+trunk: Availability condition not satisfied
      opam-ocaml-variants.5.1.1+trunk: Availability condition not satisfied
      opam-ocaml-variants.5.1.0+trunk: Availability condition not satisfied
      opam-ocaml-variants.5.0.0+trunk: Availability condition not satisfied
      ...
- opam-ocaml-variants.5.4.0+trunk -> (problem)
    Rejected candidates:
      opam-ocaml-variants.5.4.0+trunk: In same conflict class (ocaml-core-compiler) as opam-ocaml-base-compiler.5.2.0
      opam-ocaml-variants.5.2.0+trunk: Availability condition not satisfied
      opam-ocaml-variants.5.1.1+trunk: Availability condition not satisfied
      opam-ocaml-variants.5.1.0+trunk: Availability condition not satisfied
      opam-ocaml-variants.5.0.0+trunk: Availability condition not satisfied
      ...
dune exec -- bin/main.exe --repo /dev/shm/opam-giga-repository/packages   18.89s user 1.72s system 99% cpu 20.629 tot

this is new

https://github.com/RyanGibb/opam-0install-solver/commit/e396b5982ec954391670eea91173f896493a42d8

Fri
1. https://docs.google.com/document/d/19HNnqMsETTdwwQd0I0zq2rg1IrJtaoFEA1B1OpJGNUg/edit
  1. https://news.ycombinator.com/item?id=12187888
    1. > I’d suggest making some sort of meta-system packaging system that works for all the languages, but xkcd 927 (and I wouldn’t use it myself, anyway, because it would probably not install Ruby packages correctly and would solve things worse than NPM already does).
    2. > Global installs are the root of a lot of headaches when building software in the same way that global mutable state is the root of a lot of headaches when developing it.
  2. https://github.com/rust-lang/cargo/issues/2064
2. vs Nix? version resolution (using old versions of packages) and using other ecosystems
  1. decentralized package managers?
    1. using domain names?
    2. https://archive.fosdem.org/2018/schedule/event/purl/
      1. https://github.com/package-url/purl-spec in OCaml?
  2. immutable packages
    1. distrubuted append-only ledger? actually, no…
  3. https://archive.fosdem.org/2018/schedule/event/bazaarsandcathedrals/
    1. cathedral vs bazar
    2. build or runtime
    3. build, depends, pre-depends, recommends, suggests, enhances, breaks, conflicts, obsolete
    4. Sat solving
  4. https://archive.fosdem.org/2018/schedule/event/packagemangementunites/
    1. different registries
    2. a taxonomy of package management
    3. https://dl.acm.org/doi/pdf/10.1145/3347446
    4. https://research.swtch.com/vgo-mvs
Sat

https://www-users.cselabs.umn.edu/classes/Fall-2019/csci5271/papers/SRL2003-02.pdf https://dl.acm.org/doi/pdf/10.1145/3365199 https://anil.recoil.org/papers/2018-hotpost-osmose.pdf https://dl.acm.org/doi/10.1145/356678.356682

idea: shark could parametise build software configurations by domain name like nix could

get anil to deploy eon

what every happened to that shell over capnp?
Sun

Swapnil says to sell the package management as the LSP of package management. n*n -> n