The crucial change in this commit is the change to PackageFixedDeps to return a
ComponentDeps structure, rather than a flat list of dependencies, as long with
corresponding changes in ConfiguredPackage and ReadyPackage to accomodate this.

We don't actually take _advantage_ of these more fine-grained dependencies yet;
any use of

    depends

is now a use of

   CD.flatDeps . depends

but we will :)

Note that I have not updated the top-down solver, so in the output of the
top-down solver we cheat and pretend that all dependencies are library
dependencies.

In this commit we modify the _output_ of the modular solver (CP, the modular's
solver internal version of ConfiguredPackage) to have fine-grained dependency.
This doesn't yet modify the rest of cabal-install, so once we translate from CP
to ConfiguredPackage we still lose the distinctions between different kinds of
dependencies; this will be the topic of the next commit.

In the modular solver (and elsewhere) we use Data.Graph to represent the
dependency graph (and the reverse dependency graph). However, now that we have
more fine-grained dependencies, we really want an _edge-labeled_ graph, which
unfortunately it not available in the `containers` package. Therefore I've
written a very simple wrapper around Data.Graph that supports edge labels; we
don't need many fancy graph algorithms, and can still use Data.Graph on these
edged graphs when we want (by calling them on the underlying unlabeled graph),
so adding a dependency on `fgl` does not seem worth it.

The modular solver has its own representation for a package (PInfo). In this
commit we modify PInfo to keep track of the different kinds of dependencies.

This is a bit intricate because the solver also regards top-level goals as
dependencies, but of course those dependencies are not part of any 'component'
as such, unlike "real" dependencies. We model this by adding a type parameter
to FlaggedDeps and go which indicates whether or not we have component
information; crucially, underneath flag choices we _always_ have component
information available.

Consequently, the modular solver itself will not make use of the ComponentDeps
datatype (but only using the Component type, classifying components); we will
use ComponentDeps when we translate out of the results from the modular solver
into cabal-install's main datatypes.

We don't yet _return_ fine-grained dependencies from the solver; this will be
the subject of the next commit.

The ComponentDeps datatype will give us fine-grained information about the
dependencies of a package's components.  This commit just introduces the
datatype, we don't use it anywhere yet.

This commit does nothing but rearrange the Modular.Dependency module into a
number of separate sections, so that's a bit clearer to see what's what. No
actual code changes here whatsoever.

I don't know why we we constructed this graph manually here rather than calling
`graphFromEdges`; it doesn't really matter except that we will want to change
the structure of this graph somewhat once we have more fine-grained
dependencies, and then the manual construction becomes a bit more painful;
easier to use the standard construction.

This address @23Skidoo's comment
https://github.com/haskell/cabal/pull/2500#issuecomment-8703532

Since we didn't really have a unit test setup for the solver yet, this
introduces some basic tests for solver, as well as tests for independent goals
specifically.

In particular, in the definition of dependencyInconsistencies.

One slightly annoying thing is that in order to validate an install plan, we
need to know if the goals are to be considered independent. This means we need
to pass an additional Bool to a few functions; to limit the number of functions
where this is necessary, also recorded whether or not goals are independent as
part of the InstallPlan itself.

This is implemented as a separate pass so that it can be understood
independently of the rest of the solver.

POption annotates a package choice with a "linked to" field. This commit
just introduces the datatype and deals with the immediate fallout, it doesn't
actually use the field for anything.

Duncan Coutts authored 10 years ago and Edsko de Vries committed 10 years ago

It turns out not to be the right solution for general private
dependencies and is just complicated. However we keep qualified
goals, just much simpler. Now dependencies simply inherit the
qualification of their parent goal. This gets us closer to the
intended behaviour for the --independent-goals feature, and for
the simpler case of private dependencies for setup scripts.

When not using --independent-goals, the solver behaves exactly as
before (tested by comparing solver logs for a hard hackage goal).
When using --independent-goals, now every dep of each independent
goal is qualified, so the dependencies are solved completely
independently (which is actually too much still).

Handle more 'strip --version' output formats.

Fixes #2497.

-Wall police

GHC HEAD now warns about redundant constraints.

Clean up graph traversal code

The option '-fno-missing-import-lists' is available in all supported GHC
versions (looks like it was introduced in 7.0).

Fixes #2469.

Minor type class cleanup

It's now only used in cabal-install.

[ci skip]

This addresses commit commemts

* https://github.com/haskell/cabal/pull/2488#commitcomment-10373353
* https://github.com/haskell/cabal/pull/2488#commitcomment-10373373
* https://github.com/haskell/cabal/pull/2488#commitcomment-10375768

from @23Skidoo.

See https://github.com/haskell-infra/hackage-trustees/issues/4#issuecomment-85492747

[ci skip]

Take advantage in cabal-install of the new
HasInstalledPackageId/PackagedInstall split in Cabal.  The graph traversal
functions in cabal-install, previously redundant, are now back in use. Their
types match the ones in Cabal, with only the difference in the PackageInstalled
(Cabal) versus PackageFixedDeps (cabal-install) type class.

The only PackageInstalled instance left in Cabal is for InstalledPackage, which
is a thin wrapper around InstalledPackageInfo; with these refactorings in
place, InstalledPackage is there only to support the TopDown solver. The fact
that we won't have PackageInstalled instances anymore for PlanPackage and co
means that we are forced to call the correct graph traversal functions (from
cabal-install, rather than from Cabal).

Introduce ConfiguredId:

    -- | A ConfiguredId is a package ID for a configured package.
    --
    -- Once we configure a source package we know it's InstalledPackageId (at
    -- least, in principle, even if we have to fake it currently). It is still
    -- however useful in lots of places to also know the source ID for the
    -- package.  We therefore bundle the two.
    --
    -- An already installed package of course is also "configured" (all it's
    -- configuration parameters and dependencies have been specified).
    --
    -- TODO: I wonder if it would make sense to promote this datatype to Cabal
    -- and use it consistently instead of InstalledPackageIds?
    data ConfiguredId = ConfiguredId {
        confSrcId  :: PackageId
      , confInstId :: InstalledPackageId
      }

And use it for ConfiguredPackage. As the comment says, though, I wonder if we
should use this in more places.

One slightly tricky thing here is that the output of both solvers had to be
modified to keep installed package IDs where possible; in the modular solver
this was easy enough, as it does this properly, but in the top-down solver this
is a bit of a hack; however, I’ve documented the hack in detail inline in the
code.

NOTE: Although this change is currently mostly cosmetic, in the future, once we
drop the single instance restriction, it is very important that we don't
convert from installed package IDs to source IDs and then back to installed
package IDs, as this conversion will be lossy.

Give the top-down solver it's own copy of `dependencyGraph`. This means that we
now have three independent implementations of `dependencyGraph`:

- `dependencyGraph` in `Cabal` takes a package index indexed by installed
  package IDs and only has access to library dependencies.
- `dependencyGraph` in `Distribution.Client.PlanIndex` in `cabal-install` takes
  a package index indexed by installed package IDs and has access to all
  dependencies.
- `dependencyGraph` in the top-down solver in `cabal-install` takes a package
  index indexed by package _names_, and has access to all dependencies.

Ideally we would switch the top-down solver over to use a package indexed by
installed package IDs, so that this duplication could be avoided, but that's a
bit of work and the top-down solver is legacy code anyway. Can still do that
later, of course.

Moreover, this makes the top-down solver monomorphic where possible, and
introduce its own SourceDeps class so that it is independent of the FixedDeps
class (which we will change over to use InstalledPackageIds instead).

Introduce

    dependencyClosure :: InstallPlan
                      -> [PackageIdentifier]
                      -> Either (PackageIndex PlanPackage) [(PlanPackage, [InstalledPackageId])]

And use this in the definition of `pruneInstallPlan` in `freeze`, to avoid
first converting an install plan from a `Cabal.PackageIndex` to a
`CabalInstall.PackageIndex`.

This resolves the first of the two irregularities mentioned in the previous
commit.