Backpack for Stack

[ezyang]

Hello all,

I want to open up the discussion about how Backpack can be integrated with Stack; in particular, I'd be willing to work on and submit a patchset adding support for it in Stack. But before I do that, I want to hash out some general architectural concerns. The specification for the GHC and Cabal support for Backpack is here: https://github.com/ezyang/ghc-proposals/blob/backpack/proposals/0000-backpack.rst ; please read it for more motivation on why you might like to support it.

The design process over two years lead us to a design where Backpack requires the package manager (Stack) to know how to instantiate packages that have required signatures in them (I spent the better part of six months trying to figure out how to do it all in GHC; if you are interested in the sordid details I can let you know). Things seem to work most smoothly if:

1. The package manager has a component oriented build model; that is, the unit of work in the install plan is a component rather than a package. (I don't believe Stack is architected in this way, although issues like stack 0.1.8 lost ability to build individual executables or library #1406 suggest it might be a good architecture for Stack anyway.) See also https://github.com/ezyang/ghc-proposals/blob/master/proposals/0000-componentized-cabal.rst for the proposal that added per-component configure to Cabal
2. The package manager knows enough to be able to finalize the package description (i.e., resolve all of its conditionals, getting a PackageDescription); we can't do Backpack instantiation until this finalization has occurred. I don't know where in the Stack codebase one would have to engineer this.

I'll note that private use of Backpack (i.e., the public library does not have any signatures) should be supported out-of-the-box, as there is no change to the outward-facing API of Setup scripts in this case (Stack will need to understand how to register multiple libraries produced by a Setup script, however). In the meantime, public libraries which have signatures would not be supported.

One of the major applications of Backpack I would like to see in the near future is the Backpack-ification of GHC's boot libraries to solve the string problem. Backpack would make it easy to write modules which are parametric over a particular desired string representation; the original package names would continue to export String-based interfaces, but versions using ByteString etc could be made available, and the availability of a package abstracted over holes means that an end-user could specify their own. Absent full support for Backpack, Stack would at least have to be able to handle traditional-looking packages which internally depended on libraries that made use of Backpack. Maybe this would be easy.

Please let me know if you have any questions or concerns; I'd be happy to answer them.

CC @mgsloan, @snoyberg, @Blaisorblade , @borsboom , @harendra-kumar

[aljce]

This would be awesome.

[Blaisorblade]

@ezyang First let me thank you for all your work on this.

TL;DR. Does stack need this shipped tomorrow, in a month or in a year?

Before I can look into details and ask more substantive questions: is there a timeline for Backpack being merged/released/used, and an estimate how much work was required on cabal-install?

Absent full support for Backpack, Stack would at least have to be able to handle traditional-looking packages which internally depended on libraries that made use of Backpack. Maybe this would be easy.

I agree this is probably essential. Having feature parity also matters—having to choose between stack and Backpack, or stack and sane strings, would be pretty bad.

[borsboom]

@mgsloan, I think you know the most about the parts of Stack that @ezyang is talking about. Once you're back from BM, can you weigh in?

@ezyang: how is cabal-install going to handle Backpack? Both cabal-install and Stack use the Cabal library to actually build packages, so there may be opportunity to share much of the code.

[ezyang]

Does stack need this shipped tomorrow, in a month or in a year?

Definitely not tomorrow or a month. If all goes well Backpack will get merged to GHC and Cabal, and people can start experimenting with it, but there were certainly be bugs and I won't claim that anyone should start using it for real immediately. Backpack'ing base is at least blocked on teaching GHC's build system how to deal, which will take some time and I am not planning for 8.2. On the other hand, base is probably the most plausible, widely used package that will get Backpack'ed, because (1) the potential upside is so great, and (2) it closely tracks GHC versions, so we don't have to worry about supporting old GHCs.

how is cabal-install going to handle Backpack? Both cabal-install and Stack use the Cabal library to actually build packages, so there may be opportunity to share much of the code.

There are some key library functions for configuring and instantiating packages, and cabal-install (new-build only; the legacy codepath doesn't support it) just calls out to them. At present, there are some things that are duplicated because I couldn't figure out an API that could be reused in both cases, but this is definitely a case where I can try harder.

The two key functions have these signatures:

type ConfiguredComponentMap =
        (Map PackageName (ComponentId, PackageId), -- libraries
         Map String ComponentId)                   -- executables
toConfiguredComponent
    :: PackageDescription
    -> ComponentId
    -> Map PackageName (ComponentId, PackageId) -- external
    -> ConfiguredComponentMap
    -> Component
    -> ConfiguredComponent

type LinkedComponentMap = Map ComponentId (UnitId, ModuleShape)
toLinkedComponent
    :: Verbosity
    -> PackageId
    -> LinkedComponentMap
    -> ConfiguredComponent
    -> LogProgress LinkedComponent

and a LinkedComponent has all the information to actually build with Backpack (the model is that every source package produces a configured component, which is mix-in linked into a linked component; then you go ahead and instantiate all the linked components getting the final graph of build products you need to build.)

[chrisdone]

The package manager knows enough to be able to finalize the package description (i.e., resolve all of its conditionals, getting a PackageDescription); we can't do Backpack instantiation until this finalization has occurred. I don't know where in the Stack codebase one would have to engineer this.

Stack does this. We use Cabal to parse the .cabal file but then resolve the GenericPackageDescription manually. Here is an example: https://github.com/commercialhaskell/stack/blob/master/src/Stack/Package.hs#L765 The whole of Stack.Package is pretty much dedicated to resolving package info. See also https://github.com/commercialhaskell/stack/blob/master/src/Stack/Package.hs#L198

[ezyang]

Great. Another question I have (since I am looking into this) is how difficult it would be to get Stack to support a per-component build model. I'm hoping that I can take anywhere we talk about 'Package' and actually it's talking about a 'Component', but I am not familiar enough with the code to say if this is the case or not.

[mgsloan]

@ezyang Could be tricky! The current code is more package centric than component centric. This is for a variety of reasons. Off the top of my head:

1. Dependencies vary based on whether --enable-tests or --enable-benchmarks is passed to Cabal, so this needs to be figured out on a package level
2. Avoiding package reconfiguration - best to configure all the components we want at once

And no doubt, more. So, no, when the stack code is talking about a 'Package' it's definitely not talking about a 'Component'.

[ezyang]

OK. So perhaps a reasonable approach to start with is to assume that any package which exposes a Backpack library, ONLY contains that library, so that if I need to instantiate a package multiple times, this would only involve creating duplicate copies of the package (another thing where I'm not sure how well Stack will deal with this change.)

[ezyang]

I've been fishing around the codebase, and here are some initial architectural thoughts on what Backpack needs.

• Stack defines a simplified Package data type, which it reads out the contents of PackageDescription into. Backpack introduces some new fields, most notably mixins, which need to be preserved so that Backpack can figure out how packages are being instantiated. At the moment, Package doesn't really preserve any information like exposed modules which we would need to do this. It seems the most convenient way of keeping all the information Backpack needs is to keep PackageDescription verbatim in Package? This will also make it easier to call into Cabal to do mix-in linking.

• Once we have all the packages, we need to do a "mix-in" linking step to figure out exactly how packages have been instantiated. For example, if I have build-depends: regex-indef, str-string, I need to figure out that regex-indef's signature named Str was instantiated with the Str from str-string.

  It is an interesting question on how to integrate this with Stack. Stack's model is that it goes ahead and reads in all of the local source packages, but then lazily reads in the external package information using the accessor function created by withLoadPackage. The idea is that if a package is already installed, then we can avoid traversing its dependency graph. This should integrate reasonably well with Backpack: if a package is installed, we can read off the module shape (that's the metadata you need to mix-in link) from the installed package info; if it is not, we can compute it when we installPackage.

• Mix-in linking is not enough: after we figure out how everything is linked, we have to instantiate, creating a build task for every configuration by which a package was instantiated. In Stack, a build Plan consists of some number of Tasks to be done. I'm not sure how dependencies between tasks are computed, but each task is uniquely identified by the PackageIdentifier it provides (taskProvides). A Task roughly corresponds to a configure/build pair on Cabal. So, we need to modify taskProvides to be a bit more flexible: rather than only build a PackageIdentifier, it builds both a package identifier and an instantiation (to be defined shortly). Let's call such an identifier a UnitIdentifier, following the terminology I've used in Cabal and my thesis. Roughly speaking, these data structures should look like this:

  data UnitIdentifier = UnitIdentifier PackageIdentifier [(ModuleName, Module)]
  data Module = Module UnitIdentifier ModuleName
  

If Stack was modified in this way, would you take the patch? How would you like the design to be different? What is unclear?

[mgsloan]

Hey @ezyang , sorry for letting this languish, got caught up in other things. Passing this over to @snoyberg

[snoyberg]

I'm just coming up to speed on this now Edward. It seems relevant to work I'm already doing upgrading to Cabal 2.0. I'm also in favor of pushing Stack towards a component base build system. My only concern with this is making sure we retain support for building packages with older versions of Cabal, as all existing snapshots include such an older library version.

I realize this issue is a bit dated now, and perhaps you have different thoughts. Maybe we could jump on a text chat and synch up?

[ezyang]

@snoyberg Sure thing; ping me on IRC some time? As far as I am concerned, the thinking on this ticket hasn't changed much (although maybe Stack's internals have!)

My only concern with this is making sure we retain support for building packages with older versions of Cabal, as all existing snapshots include such an older library version.

Yeah, so in cabal new-build, this is done by treating these packages as non-per-component, single packages in the plan. It's a little bit of complexity but not too bad, and keeps BC.

[snoyberg]

Just chatted with @ezyang on IRC about this. Here's my summary:

1. We first need to get Cabal 2.0 support merged into Stack, which is on me (ETA: 2 weeks)
2. Once that's done, we will switch Stack to a per-component build plan. This is something that I'm very excited about in fact, see Specify components when configuring, not building haskell/cabal#2802
3. The biggest wrinkle is continuing support for pre-2.0 Cabals, which will be necessary for any LTS or Nightly release before GHC 8.2. Basic plan of attack is:
   1. Every build plan is calculated on a per-component basis
   2. If we're using Cabal 2.0 or later, we will also build on a per-component basis (separate configure with a separate dist dir for each and every component)
   3. If we're using pre-2.0 and there are no cycles in dependencies (which can happen in test suites and benchmarks), then we convert the per-component plan to a simple per-package plan and build
   4. If we're using pre-2.0 and there are cycles, we will convert into a staged per-package plan: any packages that have cycles will be split into lib/exe builds and full builds (including the tests and benchmarks). This is essentially the same as we have today, but can hopefully be streamlined by relying on the per-component plan logic. (Example use case: running stack test inside the bytestring package.)

I'll ping this issue with updates when Cabal 2.0 is merged in

[snoyberg]

Pinging appropriately: Cabal 2.0 support has just been merged to master :)

[mgsloan]

One thing for switching stack to a per-component build plan will also be adding support for internal libraries - #3361

Also support for foreign libraries, not sure if that's as relevant - #3364