Mon 2 Sep 2024

Previous: Mon 26 Aug 2024 Next: Mon 9 Sep 2024

Tue

Try dumping the SAT graph to see how big we make it

hmm, magic trace traces are empty

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

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

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