Merging `mi_exports` and `docs_structure`

[sjakobi]

The problem

mi_exports and docs_structure both contain the same AvailInfos, albeit in different order. In order to avoid bloat in the .hi-files, we'd rather serialize each AvailInfo only once.

mi_exports

mi_exports seem to be created like this:

1. They are extracted/renamed in TcRnExports.exports_from_avails.
2. Assigned to tcg_exports in tcRnExports
3. Copied to mg_exports in deSugar
4. In mkIface_, they are sorted with MkIface.mkIfaceExports and assigned to mi_exports.

Ordering of avails

The docs for mi_exports currently say:

Kept sorted by (mod,occ), to make version comparisons easier
Records the modules that are the declaration points for things
exported by this module, and the 'OccName's of those things

In order to keep the version comparisons fast, we need to ensure that the ordering of avails is deterministic.

Question: Does anything rely on the current ordering of avails that might be broken if we use export order?

In some places it might also be beneficial to have the avails in export order. For example in GHCi's :browse.

[sjakobi]

An implementation idea:

Maybe it's enough to hook into deSugar, just like extractDocs, and use a variant of mkDocStructure to create a "module structure". Depending on -haddock it will also contain docs or consist only of the avails in export order.

Naming: How about something like ModLayout?

[harpocrates]

Question: Does anything rely on the current ordering of avails that might be broken if we use export order?

Are you asking if anything is broken in GHC or in Haddock? In Haddock, I don't think so. In GHC, I'm not an expert but I think the answer is no, provided you find a way to keep the version comparison fast. You're going to have to be tread careful around the hot paths.

I'm not yet convinced that serializing both mi_exports and docs_structure is really that bad though.

If the concern is interface file size, aren't avails made up of pretty much only Name's which are anyways deduplicated in the symbol table? In other words: what is the problem you are trying to solve and what are the numbers that indicate a problem in the first place?

[sjakobi]

Are you asking if anything is broken in GHC or in Haddock? In Haddock, I don't think so. In GHC, I'm not an expert but I think the answer is no, provided you find a way to keep the version comparison fast. You're going to have to be tread careful around the hot paths.

I was mainly concerned about GHC.

I'm not yet convinced that serializing both mi_exports and docs_structure is really that bad though.

If the concern is interface file size, aren't avails made up of pretty much only Name's which are anyways deduplicated in the symbol table? In other words: what is the problem you are trying to solve and what are the numbers that indicate a problem in the first place?

Right. This was @alexbiehl's idea who – I believe – was concerned both about performance and the conceptual inelegance of duplicating this data.

Personally I'd be happy not to address this issue in the main Hi Haddock patch as long as performance stays acceptable. I'm afraid I don't currently have any performance numbers to compare though.

Even if we don't merge mi_exports and docs_structure for now, we'll need to find a deterministic and intuitive behavior for docs_structure.

[harpocrates]

I'm primarily worried about the potential for performance regressions when reading interface files which were produced with -haddock (especially in cases where the doc strings are not needed). After that, I also want the writing of interface files with -haddock to be reasonably fast and the interface file size to not dramatically increase when docstrings get included. Back to the first point though, it seems to me that the easiest way to avoid a regression in that case is to not change how mi_exports currently works.

Even if we don't merge mi_exports and docs_structure for now, we'll need to find a deterministic and intuitive behavior for docs_structure.

I don't see the difficulty - can't you just do the same thing that mkIfaceExports does, except not sort the final [AvailInfo]? More concretely (and unceremoniously duplicating code from mkIfaceExports):

mkDeterministicDocStructure :: DocStructure -> DocStructure
mkDeterministicDocStructure = map go
  where
  go :: DocStructureItem -> DocStructureItem
  go (DsiExports avails) = DsiExports (map sort_subs avails)
  go dsi = dsi

  -- copied from `mkIfaceExports`
  sort_subs :: AvailInfo -> AvailInfo
  sort_subs (Avail n) = Avail n
  sort_subs (AvailTC n [] fs) = AvailTC n [] (sort_flds fs)
  sort_subs (AvailTC n (m:ms) fs)
     | n==m      = AvailTC n (m:sortBy stableNameCmp ms) (sort_flds fs)
     | otherwise = AvailTC n (sortBy stableNameCmp (m:ms)) (sort_flds fs)

  -- copied from `mkIfaceExports`
  sort_flds = sortBy (stableNameCmp `on` flSelector)

[sjakobi]

it seems to me that the easiest way to avoid a regression in that case is to not change how mi_exports currently works.

Right. It seems quite possible that the performance impact of sorting the Avails for each use of mi_exports would still be acceptable.

can't you just do the same thing that mkIfaceExports does, except not sort the final [AvailInfo]?

I kind of want to have the Avails (and the Names within) in the .hi-files in a "canonical" order, that should be as close as possible to the order in which the programmer wants to expose them. For example, I hope that haddock can basically mapM over them in order to generate its module representation.

For this it is necessary, that the AvailInfos themselves are also in their original or exported order:
I think it would be nicer to have the Names within the AvailInfos sorted in export order too. I still need to figure out how to get that order though…

[harpocrates]

Right. It seems quite possible that the performance impact of sorting the Avails for each use of mi_exports would still be acceptable.

I find it tough to believe this is going to be possible in general (especially with modules that export a pathological number of things).

I kind of want to have the Avails (and the Names within) in the .hi-files in a "canonical" order, that should be as close as possible to the order in which the programmer wants to expose them. For example, I hope that haddock can basically mapM over them in order to generate its module representation.

Just to be be clear, are you suggesting that the order of sub-avails (Name's within) in export lists impact the final Haddock output? For instance, would you want Haddock to list C2 before C1 given the following input?

module Test ( T(C2,C1) )where

data T = C1 | C2

What about records?

module Test ( F(c2,c1,T) ) where

data F = T { c1 :: Int, c2 :: Bool }

I think I disagree with you here. I'd expect sub avails (Name's within) should always be ordered based on the reified GHC decl (so the order in which you serialize these in docs_structure doesn't matter, beyond making sure it is a deterministic order). The order of AvailInfo's, on the other hand, should definitely be sorted in export order.