+++ /dev/null
-%
-% (c) The OBFUSCATION-THROUGH-GRATUITOUS-PREPROCESSOR-ABUSE Project,
-% Glasgow University, 1990-2000
-%
-
-% \documentstyle[preprint]{acmconf}
-\documentclass[11pt]{article}
-\oddsidemargin 0.1 in % Note that \oddsidemargin = \evensidemargin
-\evensidemargin 0.1 in
-\marginparwidth 0.85in % Narrow margins require narrower marginal notes
-\marginparsep 0 in
-\sloppy
-
-%\usepackage{epsfig}
-\usepackage{shortvrb}
-\MakeShortVerb{\@}
-
-%\newcommand{\note}[1]{{\em Note: #1}}
-\newcommand{\note}[1]{{{\bf Note:}\sl #1}}
-\newcommand{\ToDo}[1]{{{\bf ToDo:}\sl #1}}
-\newcommand{\Arg}[1]{\mbox{${\tt arg}_{#1}$}}
-\newcommand{\bottom}{\perp}
-
-\newcommand{\secref}[1]{Section~\ref{sec:#1}}
-\newcommand{\figref}[1]{Figure~\ref{fig:#1}}
-\newcommand{\Section}[2]{\section{#1}\label{sec:#2}}
-\newcommand{\Subsection}[2]{\subsection{#1}\label{sec:#2}}
-\newcommand{\Subsubsection}[2]{\subsubsection{#1}\label{sec:#2}}
-
-% DIMENSION OF TEXT:
-\textheight 8.5 in
-\textwidth 6.25 in
-
-\topmargin 0 in
-\headheight 0 in
-\headsep .25 in
-
-
-\setlength{\parskip}{0.15cm}
-\setlength{\parsep}{0.15cm}
-\setlength{\topsep}{0cm} % Reduces space before and after verbatim,
- % which is implemented using trivlist
-\setlength{\parindent}{0cm}
-
-\renewcommand{\textfraction}{0.2}
-\renewcommand{\floatpagefraction}{0.7}
-
-\begin{document}
-
-\title{The GHCi Draft Design, round 2}
-\author{MSR Cambridge Haskell Crew \\
- Microsoft Research Ltd., Cambridge}
-
-\maketitle
-
-%%%\tableofcontents
-%%%\newpage
-
-%%-----------------------------------------------------------------%%
-\section{Details}
-
-\subsection{Outline of the design}
-\label{sec:details-intro}
-
-The design falls into three major parts:
-\begin{itemize}
-\item The compilation manager (CM), which coordinates the
- system and supplies a HEP-like interface to clients.
-\item The module compiler (@compile@), which translates individual
- modules to interpretable or machine code.
-\item The linker (@link@),
- which maintains the executable image in interpreted mode.
-\end{itemize}
-
-There are also three auxiliary parts: the finder, which locates
-source, object and interface files, the summariser, which quickly
-finds dependency information for modules, and the static info
-(compiler flags and package details), which is unchanged over the
-course of a session.
-
-This section continues with an overview of the session-lifetime data
-structures. Then follows the finder (section~\ref{sec:finder}),
-summariser (section~\ref{sec:summariser}),
-static info (section~\ref{sec:staticinfo}),
-and finally the three big sections
-(\ref{sec:manager},~\ref{sec:compiler},~\ref{sec:linker})
-on the compilation manager, compiler and linker respectively.
-
-\subsubsection*{Some terminology}
-
-Lifetimes: the phrase {\bf session lifetime} covers a complete run of
-GHCI, encompassing multiple recompilation runs. {\bf Module lifetime}
-is a lot shorter, being that of data needed to translate a single
-module, but then discarded, for example Core, AbstractC, Stix trees.
-
-Data structures with module lifetime are well documented and understood.
-This document is mostly concerned with session-lifetime data.
-Most of these structures are ``owned'' by CM, since that's
-the only major component of GHCI which deals with session-lifetime
-issues.
-
-Modules and packages: {\bf home} refers to modules in this package,
-precisely the ones tracked and updated by the compilation manager.
-{\bf Package} refers to all other packages, which are assumed static.
-
-\subsubsection*{A summary of all session-lifetime data structures}
-
-These structures have session lifetime but not necessarily global
-visibility. Subsequent sections elaborate who can see what.
-\begin{itemize}
-\item {\bf Home Symbol Table (HST)} (owner: CM) holds the post-renaming
- environments created by compiling each home module.
-\item {\bf Home Interface Table (HIT)} (owner: CM) holds in-memory
- representations of the interface file created by compiling
- each home module.
-\item {\bf Unlinked Images (UI)} (owner: CM) are executable but as-yet
- unlinked translations of home modules only.
-\item {\bf Module Graph (MG)} (owner: CM) is the current module graph.
-\item {\bf Static Info (SI)} (owner: CM) is the package configuration
- information (PCI) and compiler flags (FLAGS).
-\item {\bf Persistent Compiler State (PCS)} (owner: @compile@)
- is @compile@'s private cache of information about package
- modules.
-\item {\bf Persistent Linker State (PLS)} (owner: @link@) is
- @link@'s private information concerning the the current
- state of the (in-memory) executable image.
-\end{itemize}
-
-
-%%-- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --%%
-\subsection{The finder (\mbox{\tt type Finder})}
-\label{sec:finder}
-
-@Path@ could be an indication of a location in a filesystem, or it
-could be some more generic kind of resource identifier, a URL for
-example.
-\begin{verbatim}
- data Path = ...
-\end{verbatim}
-
-And some names. @Module@s are now used as primary keys for various
-maps, so they are given a @Unique@.
-\begin{verbatim}
- type ModName = String -- a module name
- type PkgName = String -- a package name
- type Module = -- contains ModName and a Unique, at least
-\end{verbatim}
-
-A @ModLocation@ says where a module is, what it's called and in what
-form it is.
-\begin{verbatim}
- data ModLocation = SourceOnly Module Path -- .hs
- | ObjectCode Module Path Path -- .o, .hi
- | InPackage Module PkgName
- -- examine PCI to determine package Path
-\end{verbatim}
-
-The module finder generates @ModLocation@s from @ModName@s. We expect
-it will assume packages to be static, but we want to be able to track
-changes in home modules during the session. Specifically, we want to
-be able to notice that a module's object and interface have been
-updated, presumably by a compile run outside of the GHCI session.
-Hence the two-stage type:
-\begin{verbatim}
- type Finder = ModName -> IO ModLocation
- newFinder :: PCI -> IO Finder
-\end{verbatim}
-@newFinder@ examines the package information right at the start, but
-returns an @IO@-typed function which can inspect home module changes
-later in the session.
-
-
-%%-- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --%%
-\subsection{The summariser (\mbox{\tt summarise})}
-\label{sec:summariser}
-
-A @ModSummary@ records the minimum information needed to establish the
-module graph and determine whose source has changed. @ModSummary@s
-can be created quickly.
-\begin{verbatim}
- data ModSummary = ModSummary
- ModLocation -- location and kind
- (Maybe (String, Fingerprint))
- -- source and fingerprint if .hs
- (Maybe [ModName]) -- imports if .hs or .hi
-
- type Fingerprint = ... -- file timestamp, or source checksum?
-
- summarise :: ModLocation -> IO ModSummary
-\end{verbatim}
-
-The summary contains the location and source text, and the location
-contains the name. We would like to remove the assumption that
-sources live on disk, but I'm not sure this is good enough yet.
-
-\ToDo{Should @ModSummary@ contain source text for interface files too?}
-\ToDo{Also say that @ModIFace@ contains its module's @ModSummary@ (why?).}
-
-
-%%-- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --%%
-\subsection{Static information (SI)}
-\label{sec:staticinfo}
-
-PCI, the package configuration information, is a list of @PkgInfo@,
-each containing at least the following:
-\begin{verbatim}
- data PkgInfo
- = PkgInfo PkgName -- my name
- Path -- path to my base location
- [PkgName] -- who I depend on
- [ModName] -- modules I supply
- [Unlinked] -- paths to my object files
-
- type PCI = [PkgInfo]
-\end{verbatim}
-The @Path@s in it, including those in the @Unlinked@s, are set up
-when GHCI starts.
-
-FLAGS is a bunch of compiler options. We haven't figured out yet how
-to partition them into those for the whole session vs those for
-specific source files, so currently the best we can do is:
-\begin{verbatim}
- data FLAGS = ...
-\end{verbatim}
-
-The static information (SI) is the both of these:
-\begin{verbatim}
- data SI = SI PCI
- FLAGS
-\end{verbatim}
-
-
-
-%%-- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --%%
-\subsection{The Compilation Manager (CM)}
-\label{sec:manager}
-
-\subsubsection{Data structures owned by CM}
-
-CM maintains two maps (HST, HIT) and a set (UI). It's important to
-realise that CM only knows about the map/set-ness, and has no idea
-what a @ModDetails@, @ModIFace@ or @Linkable@ is. Only @compile@ and
-@link@ know that, and CM passes these types around without
-inspecting them.
-
-\begin{itemize}
-\item
- {\bf Home Symbol Table (HST)} @:: FiniteMap Module ModDetails@
-
- The @ModDetails@ (a couple of layers down) contain tycons, classes,
- instances, etc, collectively known as ``entities''. Referrals from
- other modules to these entities is direct, with no intervening
- indirections of any kind; conversely, these entities refer directly
- to other entities, regardless of module boundaries. HST only holds
- information for home modules; the corresponding wired-up details
- for package (non-home) modules are created on demand in the package
- symbol table (PST) inside the persistent compiler's state (PCS).
-
- CM maintains the HST, which is passed to, but not modified by,
- @compile@. If compilation of a module is successful, @compile@
- returns the resulting @ModDetails@ (inside the @CompResult@) which
- CM then adds to HST.
-
- CM throws away arbitrarily large parts of HST at the start of a
- rebuild, and uses @compile@ to incrementally reconstruct it.
-
-\item
- {\bf Home Interface Table (HIT)} @:: FiniteMap Module ModIFace@
-
- (Completely private to CM; nobody else sees this).
-
- Compilation of a module always creates a @ModIFace@, which contains
- the unlinked symbol table entries. CM maintains this @FiniteMap@
- @ModName@ @ModIFace@, with session lifetime. CM never throws away
- @ModIFace@s, but it does update them, by passing old ones to
- @compile@ if they exist, and getting new ones back.
-
- CM acquires @ModuleIFace@s from @compile@, which it only applies
- to modules in the home package. As a result, HIT only contains
- @ModuleIFace@s for modules in the home package. Those from other
- packages reside in the package interface table (PIT) which is a
- component of PCS.
-
-\item
- {\bf Unlinked Images (UI)} @:: Set Linkable@
-
- The @Linkable@s in UI represent executable but as-yet unlinked
- module translations. A @Linkable@ can contain the name of an
- object, archive or DLL file. In interactive mode, it may also be
- the STG trees derived from translating a module. So @compile@
- returns a @Linkable@ from each successful run, namely that of
- translating the module at hand.
-
- At link-time, CM supplies @Linkable@s for the upwards closure of
- all packages which have changed, to @link@. It also examines the
- @ModSummary@s for all home modules, and by examining their imports
- and the SI.PCI (package configuration info) it can determine the
- @Linkable@s from all required imported packages too.
-
- @Linkable@s and @ModIFace@s have a close relationship. Each
- translated module has a corresponding @Linkable@ somewhere.
- However, there may be @Linkable@s with no corresponding modules
- (the RTS, for example). Conversely, multiple modules may share a
- single @Linkable@ -- as is the case for any module from a
- multi-module package. For these reasons it seems appropriate to
- keep the two concepts distinct. @Linkable@s also provide
- information about the sequence in which individual package
- components should be linked, and that isn't the business of any
- specific module to know.
-
- CM passes @compile@ a module's old @ModIFace@, if it has one, in
- the hope that the module won't need recompiling. If so, @compile@
- can just return the new @ModDetails@ created from it, and CM will
- re-use the old @ModIFace@. If the module {\em is} recompiled (or
- scheduled to be loaded from disk), @compile@ returns both the
- new @ModIFace@ and new @Linkable@.
-
-\item
- {\bf Module Graph (MG)} @:: known-only-to-CM@
-
- Records, for CM's purposes, the current module graph,
- up-to-dateness and summaries. More details when I get to them.
- Only contains home modules.
-\end{itemize}
-Probably all this stuff is rolled together into the Persistent CM
-State (PCMS):
-\begin{verbatim}
- data PCMS = PCMS HST HIT UI MG
- emptyPCMS :: IO PCMS
-\end{verbatim}
-
-\subsubsection{What CM implements}
-It pretty much implements the HEP interface. First, though, define a
-containing structure for the state of the entire CM system and its
-subsystems @compile@ and @link@:
-\begin{verbatim}
- data CmState
- = CmState PCMS -- CM's stuff
- PCS -- compile's stuff
- PLS -- link's stuff
- SI -- the static info, never changes
- Finder -- the finder
-\end{verbatim}
-
-The @CmState@ is threaded through the HEP interface. In reality
-this might be done using @IORef@s, but for clarity:
-\begin{verbatim}
- type ModHandle = ... (opaque to CM/HEP clients) ...
- type HValue = ... (opaque to CM/HEP clients) ...
-
- cmInit :: FLAGS
- -> [PkgInfo]
- -> IO CmState
-
- cmLoadModule :: CmState
- -> ModName
- -> IO (CmState, Either [SDoc] ModHandle)
-
- cmGetExpr :: ModHandle
- -> CmState
- -> String -> IO (CmState, Either [SDoc] HValue)
-
- cmRunExpr :: HValue -> IO () -- don't need CmState here
-\end{verbatim}
-Almost all the huff and puff in this document pertains to @cmLoadModule@.
-
-
-\subsubsection{Implementing \mbox{\tt cmInit}}
-@cmInit@ creates an empty @CmState@ using @emptyPCMS@, @emptyPCS@,
-@emptyPLS@, making SI from the supplied flags and package info, and
-by supplying the package info the @newFinder@.
-
-
-\subsubsection{Implementing \mbox{\tt cmLoadModule}}
-
-\begin{enumerate}
-\item {\bf Downsweep:} using @finder@ and @summarise@, chase from
- the given module to
- establish the new home module graph (MG). Do not chase into
- package modules.
-\item Remove from HIT, HST, UI any modules in the old MG which are
- not in the new one. The old MG is then replaced by the new one.
-\item Topologically sort MG to generate a bottom-to-top traversal
- order, giving a worklist.
-\item {\bf Upsweep:} call @compile@ on each module in the worklist in
- turn, passing it
- the ``correct'' HST, PCS, the old @ModIFace@ if
- available, and the summary. ``Correct'' HST in the sense that
- HST contains only the modules in the this module's downward
- closure, so that @compile@ can construct the correct instance
- and rule environments simply as the union of those in
- the module's downward closure.
-
- If @compile@ doesn't return a new interface/linkable pair,
- compilation wasn't necessary. Either way, update HST with
- the new @ModDetails@, and UI and HIT respectively if a
- compilation {\em did} occur.
-
- Keep going until the root module is successfully done, or
- compilation fails.
-
-\item If the previous step terminated because compilation failed,
- define the successful set as those modules in successfully
- completed SCCs, i.e. all @Linkable@s returned by @compile@ excluding
- those from modules in any cycle which includes the module which failed.
- Remove from HST, HIT, UI and MG all modules mentioned in MG which
- are not in the successful set. Call @link@ with the successful
- set,
- which should succeed. The net effect is to back off to a point
- in which those modules which are still aboard are correctly
- compiled and linked.
-
- If the previous step terminated successfully,
- call @link@ passing it the @Linkable@s in the upward closure of
- all those modules for which @compile@ produced a new @Linkable@.
-\end{enumerate}
-As a small optimisation, do this:
-\begin{enumerate}
-\item[3a.] Remove from the worklist any module M where M's source
- hasn't changed and neither has the source of any module in M's
- downward closure. This has the effect of not starting the upsweep
- right at the bottom of the graph when that's not needed.
- Source-change checking can be done quickly by CM by comparing
- summaries of modules in MG against corresponding
- summaries from the old MG.
-\end{enumerate}
-
-
-%%-- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --%%
-\subsection{The compiler (\mbox{\tt compile})}
-\label{sec:compiler}
-
-\subsubsection{Data structures owned by \mbox{\tt compile}}
-
-{\bf Persistent Compiler State (PCS)} @:: known-only-to-compile@
-
-This contains info about foreign packages only, acting as a cache,
-which is private to @compile@. The cache never becomes out of
-date. There are three parts to it:
-
- \begin{itemize}
- \item
- {\bf Package Interface Table (PIT)} @:: FiniteMap Module ModIFace@
-
- @compile@ reads interfaces from modules in foreign packages, and
- caches them in the PIT. Subsequent imports of the same module get
- them directly out of the PIT, avoiding slow lexing/parsing phases.
- Because foreign packages are assumed never to become out of date,
- all contents of PIT remain valid forever. @compile@ of course
- tries to find package interfaces in PIT in preference to reading
- them from files.
-
- Both successful and failed runs of @compile@ can add arbitrary
- numbers of new interfaces to the PIT. The failed runs don't matter
- because we assume that packages are static, so the data cached even
- by a failed run is valid forever (ie for the rest of the session).
-
- \item
- {\bf Package Symbol Table (PST)} @:: FiniteMap Module ModDetails@
-
- Adding an package interface to PIT doesn't make it directly usable
- to @compile@, because it first needs to be wired (renamed +
- typechecked) into the sphagetti of the HST. On the other hand,
- most modules only use a few entities from any imported interface,
- so wiring-in the interface at PIT-entry time might be a big time
- waster. Also, wiring in an interface could mean reading other
- interfaces, and we don't want to do that unnecessarily.
-
- The PST avoids these problems by allowing incremental wiring-in to
- happen. Pieces of foreign interfaces are copied out of the holding
- pen (HP), renamed, typechecked, and placed in the PST, but only as
- @compile@ discovers it needs them. In the process of incremental
- renaming/typechecking, @compile@ may need to read more package
- interfaces, which are added to the PIT and hence to
- HP.~\ToDo{How? When?}
-
- CM passes the PST to @compile@ and is returned an updated version
- on both success and failure.
-
- \item
- {\bf Holding Pen (HP)} @:: HoldingPen@
-
- HP holds parsed but not-yet renamed-or-typechecked fragments of
- package interfaces. As typechecking of other modules progresses,
- fragments are removed (``slurped'') from HP, renamed and
- typechecked, and placed in PCS.PST (see above). Slurping a
- fragment may require new interfaces to be read into HP. The hope
- is, though, that many fragments will never get slurped, reducing
- the total number of interfaces read (as compared to eager slurping).
-
- \end{itemize}
-
- PCS is opaque to CM; only @compile@ knows what's in it, and how to
- update it. Because packages are assumed static, PCS never becomes
- out of date. So CM only needs to be able to create an empty PCS,
- with @emptyPCS@, and thence just passes it through @compile@ with
- no further ado.
-
- In return, @compile@ must promise not to store in PCS any
- information pertaining to the home modules. If it did so, CM would
- need to have a way to remove this information prior to commencing a
- rebuild, which conflicts with PCS's opaqueness to CM.
-
-
-
-
-\subsubsection{What {\tt compile} does}
-@compile@ is necessarily somewhat complex. We've decided to do away
-with private global variables -- they make the design specification
-less clear, although the implementation might use them. Without
-further ado:
-\begin{verbatim}
- compile :: SI -- obvious
- -> Finder -- to find modules
- -> ModSummary -- summary, including source
- -> Maybe ModIFace
- -- former summary, if avail
- -> HST -- for home module ModDetails
- -> PCS -- IN: the persistent compiler state
-
- -> IO CompResult
-
- data CompResult
- = CompOK ModDetails -- new details (== HST additions)
- (Maybe (ModIFace, Linkable))
- -- summary and code; Nothing => compilation
- -- not needed (old summary and code are still valid)
- PCS -- updated PCS
- [SDoc] -- warnings
-
- | CompErrs PCS -- updated PCS
- [SDoc] -- warnings and errors
-
- data PCS
- = MkPCS PIT -- package interfaces
- PST -- post slurping global symtab contribs
- HoldingPen -- pre slurping interface bits and pieces
-
- emptyPCS :: IO PCS -- since CM has no other way to make one
-\end{verbatim}
-Although @compile@ is passed three of the global structures (FLAGS,
-HST and PCS), it only modifies PCS. The rest are modified by CM as it
-sees fit, from the stuff returned in the @CompResult@.
-
-@compile@ is allowed to return an updated PCS even if compilation
-errors occur, since the information in it pertains only to foreign
-packages and is assumed to be always-correct.
-
-What @compile@ does: \ToDo{A bit vague ... needs refining. How does
- @finder@ come into the game?}
-\begin{itemize}
-\item Figure out if this module needs recompilation.
- \begin{itemize}
- \item If there's no old @ModIFace@, it does. Else:
- \item Compare the @ModSummary@ supplied with that in the
- old @ModIFace@. If the source has changed, recompilation
- is needed. Else:
- \item Compare the usage version numbers in the old @ModIFace@ with
- those in the imported @ModIFace@s. All needed interfaces
- for this should be in either HIT or PIT. If any version
- numbers differ, recompilation is needed.
- \item Otherwise it isn't needed.
- \end{itemize}
-
-\item
- If recompilation is not needed, create a new @ModDetails@ from the
- old @ModIFace@, looking up information in HST and PCS.PST as
- necessary. Return the new details, a @Nothing@ denoting
- compilation was not needed, the PCS \ToDo{I don't think the PCS
- should be updated, but who knows?}, and an empty warning list.
-
-\item
- Otherwise, compilation is needed.
-
- If the module is only available in object+interface form, read the
- interface, make up details, create a linkable pointing at the
- object code. \ToDo{Does this involve reading any more interfaces? Does
- it involve updating PST?}
-
- Otherwise, translate from source, then create and return: an
- details, interface, linkable, updated PST, and warnings.
-
- When looking for a new interface, search HST, then PCS.PIT, and only
- then read from disk. In which case add the new interface(s) to
- PCS.PIT.
-
- \ToDo{If compiling a module with a boot-interface file, check the
- boot interface against the inferred interface.}
-\end{itemize}
-
-
-\subsubsection{Contents of \mbox{\tt ModDetails},
- \mbox{\tt ModIFace} and \mbox{\tt HoldingPen}}
-Only @compile@ can see inside these three types -- they are opaque to
-everyone else. @ModDetails@ holds the post-renaming,
-post-typechecking environment created by compiling a module.
-
-\begin{verbatim}
- data ModDetails
- = ModDetails {
- moduleExports :: Avails
- moduleEnv :: GlobalRdrEnv -- == FM RdrName [Name]
- typeEnv :: FM Name TyThing -- TyThing is in TcEnv.lhs
- instEnv :: InstEnv
- fixityEnv :: FM Name Fixity
- ruleEnv :: FM Id [Rule]
- }
-\end{verbatim}
-
-@ModIFace@ is nearly the same as @ParsedIFace@ from @RnMonad.lhs@:
-\begin{verbatim}
- type ModIFace = ParsedIFace -- not really, but ...
- data ParsedIface
- = ParsedIface {
- pi_mod :: Module, -- Complete with package info
- pi_vers :: Version, -- Module version number
- pi_orphan :: WhetherHasOrphans, -- Whether this module has orphans
- pi_usages :: [ImportVersion OccName], -- Usages
- pi_exports :: [ExportItem], -- Exports
- pi_insts :: [RdrNameInstDecl], -- Local instance declarations
- pi_decls :: [(Version, RdrNameHsDecl)], -- Local definitions
- pi_fixity :: (Version, [RdrNameFixitySig]), -- Local fixity declarations,
- -- with their version
- pi_rules :: (Version, [RdrNameRuleDecl]), -- Rules, with their version
- pi_deprecs :: [RdrNameDeprecation] -- Deprecations
- }
-\end{verbatim}
-
-@HoldingPen@ is a cleaned-up version of that found in @RnMonad.lhs@,
-retaining just the 3 pieces actually comprising the holding pen:
-\begin{verbatim}
- data HoldingPen
- = HoldingPen {
- iDecls :: DeclsMap, -- A single, global map of Names to decls
-
- iInsts :: IfaceInsts,
- -- The as-yet un-slurped instance decls; this bag is depleted when we
- -- slurp an instance decl so that we don't slurp the same one twice.
- -- Each is 'gated' by the names that must be available before
- -- this instance decl is needed.
-
- iRules :: IfaceRules
- -- Similar to instance decls, only for rules
- }
-\end{verbatim}
-
-%%-- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --%%
-\subsection{The linker (\mbox{\tt link})}
-\label{sec:linker}
-
-\subsubsection{Data structures owned by the linker}
-
-In the same way that @compile@ has a persistent compiler state (PCS),
-the linker has a persistent (session-lifetime) state, PLS, the
-Linker's Persistent State. In batch mode PLS is entirely irrelevant,
-because there is only a single link step, and can be a unit value
-ignored by everybody. In interactive mode PLS is composed of the
-following three parts:
-
-\begin{itemize}
-\item
-\textbf{The Source Symbol Table (SST)}@ :: FiniteMap RdrName HValue@
- The source symbol table is used when linking interpreted code.
- Unlinked interpreted code consists of an STG tree where
- the leaves are @RdrNames@. The linker's job is to resolve these to
- actual addresses (the alternative is to resolve these lazily when
- the code is run, but this requires passing the full symbol table
- through the interpreter and the repeated lookups will probably be
- expensive).
-
- The source symbol table therefore maps @RdrName@s to @HValue@s, for
- every @RdrName@ that currently \emph{has} an @HValue@, including all
- exported functions from object code modules that are currently
- linked in. Linking therefore turns a @StgTree RdrName@ into an
- @StgTree HValue@.
-
- It is important that we can prune this symbol table by throwing away
- the mappings for an entire module, whenever we recompile/relink a
- given module. The representation is therefore probably a two-level
- mapping, from module names, to function/constructor names, to
- @HValue@s.
-
-\item \textbf{The Object Symbol Table (OST)}@ :: FiniteMap String Addr@
- This is a lower level symbol table, mapping symbol names in object
- modules to their addresses in memory. It is used only when
- resolving the external references in an object module, and contains
- only entries that are defined in object modules.
-
- Why have two symbol tables? Well, there is a clear distinction
- between the two: the source symbol table maps Haskell symbols to
- Haskell values, and the object symbol table maps object symbols to
- addresses. There is some overlap, in that Haskell symbols certainly
- have addresses, and we could look up a Haskell symbol's address by
- manufacturing the right object symbol and looking that up in the
- object symbol table, but this is likely to be slow and would force
- us to extend the object symbol table with all the symbols
- ``exported'' by interpreted code. Doing it this way enables us to
- decouple the object management subsystem from the rest of the linker
- with a minimal interface; something like
-
- \begin{verbatim}
- loadObject :: Unlinked -> IO Object
- unloadModule :: Unlinked -> IO ()
- lookupSymbol :: String -> IO Addr
- \end{verbatim}
-
- Rather unfortunately we need @lookupSymbol@ in order to populate the
- source symbol table when linking in a new compiled module. Our
- object management subsystem is currently written in C, so decoupling
- this interface as much as possible is highly desirable.
-
-\item
- {\bf Linked Image (LI)} @:: no-explicit-representation@
-
- LI isn't explicitly represented in the system, but we record it
- here for completeness anyway. LI is the current set of
- linked-together module, package and other library fragments
- constituting the current executable mass. LI comprises:
- \begin{itemize}
- \item Machine code (@.o@, @.a@, @.DLL@ file images) in memory.
- These are loaded from disk when needed, and stored in
- @malloc@ville. To simplify storage management, they are
- never freed or reused, since this creates serious
- complications for storage management. When no longer needed,
- they are simply abandoned. New linkings of the same object
- code produces new copies in memory. We hope this not to be
- too much of a space leak.
- \item STG trees, which live in the GHCI heap and are managed by the
- storage manager in the usual way. They are held alive (are
- reachable) via the @HValue@s in the OST. Such @HValue@s are
- applications of the interpreter function to the trees
- themselves. Linking a tree comprises travelling over the
- tree, replacing all the @Id@s with pointers directly to the
- relevant @_closure@ labels, as determined by searching the
- OST. Once the leaves are linked, trees are wrapped with the
- interpreter function. The resulting @HValue@s then behave
- indistinguishably from compiled versions of the same code.
- \end{itemize}
- Because object code is outside the heap and never deallocated,
- whilst interpreted code is held alive via the HST, there's no need
- to have a data structure which ``is'' the linked image.
-
- For batch compilation, LI doesn't exist because OST doesn't exist,
- and because @link@ doesn't load code into memory, instead just
- invokes the system linker.
-
- \ToDo{Do we need to say anything about CAFs and SRTs? Probably ...}
-\end{itemize}
-As with PCS, CM has no way to create an initial PLS, so we supply
-@emptyPLS@ for that purpose.
-
-\subsubsection{The linker's interface}
-
-In practice, the PLS might be hidden in the I/O monad rather
-than passed around explicitly. (The same might be true for PCS).
-Anyway:
-
-\begin{verbatim}
- data PLS -- as described above; opaque to everybody except the linker
-
- link :: PCI -> ??? -> [[Linkable]] -> PLS -> IO LinkResult
-
- data LinkResult = LinkOK PLS
- | LinkErrs PLS [SDoc]
-
- emptyPLS :: IO PLS -- since CM has no other way to make one
-\end{verbatim}
-
-CM uses @link@ as follows:
-
-After repeatedly using @compile@ to compile all modules which are
-out-of-date, the @link@ is invoked. The @[[Linkable]]@ argument to
-@link@ represents the list of (recursive groups of) home modules which
-have been newly compiled, along with @Linkable@s for each of
-the packages in use (the compilation manager knows which external
-packages are referenced by the home package). The order of the list
-is important: it is sorted in such a way that linking any prefix of
-the list will result in an image with no unresolved references. Note
-that for batch linking there may be further restrictions; for example
-it may not be possible to link recursive groups containing libraries.
-
-@link@ does the following:
-
-\begin{itemize}
- \item
- In batch mode, do nothing. In interactive mode,
- examine the supplied @[[Linkable]]@ to determine which home
- module @Unlinked@s are new. Remove precisely these @Linkable@s
- from PLS. (In fact we really need to remove their upwards
- transitive closure, but I think it is an invariant that CM will
- supply an upwards transitive closure of new modules).
- See below for descriptions of @Linkable@ and @Unlinked@.
-
- \item
- Batch system: invoke the external linker to link everything in one go.
- Interactive: bind the @Unlinked@s for the newly compiled modules,
- plus those for any newly required packages, into PLS.
-
- Note that it is the linker's responsibility to remember which
- objects and packages have already been linked. By comparing this
- with the @Linkable@s supplied to @link@, it can determine which
- of the linkables in LI are out of date
-\end{itemize}
-
-If linking in of a group should fail for some reason, @link@ should
-not modify its PLS at all. In other words, linking each group
-is atomic; it either succeeds or fails.
-
-\subsubsection*{\mbox{\tt Unlinked} and \mbox{\tt Linkable}}
-
-Two important types: @Unlinked@ and @Linkable@. The latter is a
-higher-level representation involving multiple of the former.
-An @Unlinked@ is a reference to unlinked executable code, something
-a linker could take as input:
-
-\begin{verbatim}
- data Unlinked = DotO Path
- | DotA Path
- | DotDLL Path
- | Trees [StgTree RdrName]
-\end{verbatim}
-
-The first three describe the location of a file (presumably)
-containing the code to link. @Trees@, which only exists in
-interactive mode, gives a list of @StgTrees@, in which the unresolved
-references are @RdrNames@ -- hence it's non-linkedness. Once linked,
-those @RdrNames@ are replaced with pointers to the machine code
-implementing them.
-
-A @Linkable@ gathers together several @Unlinked@s and associates them
-with either a module or package:
-
-\begin{verbatim}
- data Linkable = LM Module [Unlinked] -- a module
- | LP PkgName -- a package
-\end{verbatim}
-
-The order of the @Unlinked@s in the list is important, as
-they are linked in left-to-right order. The @Unlinked@ objects for a
-particular package can be obtained from the package configuration (see
-Section \ref{sec:staticinfo}).
-
-\ToDo{When adding @Addr@s from an object module to SST, we need to
- somehow find out the @RdrName@s of the symbols exported by that
- module.
- So we'd need to pass in the @ModDetails@ or @ModIFace@ or some such?}
-
-
-
-%%-----------------------------------------------------------------%%
-\section{Background ideas}
-\subsubsection*{Out of date, but correct in spirit}
-
-\subsection{Restructuring the system}
-
-At the moment @hsc@ compiles one source module into C or assembly.
-This functionality is pushed inside a function called @compile@,
-introduced shortly. The main new chunk of code is CM, the compilation manager,
-which supervises multiple runs of @compile@ so as to create up-to-date
-translations of a whole bunch of modules, as quickly as possible.
-CM also employs some minor helper functions, @finder@, @summarise@ and
-@link@, to do its work.
-
-Our intent is to allow CM to be used as the basis either of a
-multi-module, batch mode compilation system, or to supply an
-interactive environment similar to that of Hugs.
-Only minor modifications to the behaviour of @compile@ and @link@
-are needed to give these different behaviours.
-
-CM and @compile@, and, for interactive use, an interpreter, are the
-main code components. The most important data structure is the global
-symbol table; much design effort has been expended thereupon.
-
-
-\subsection{How the global symbol table is implemented}
-
-The top level symbol table is a @FiniteMap@ @ModuleName@
-@ModuleDetails@. @ModuleDetails@ contains essentially the environment
-created by compiling a module. CM manages this finite map, adding and
-deleting module entries as required.
-
-The @ModuleDetails@ for a module @M@ contains descriptions of all
-tycons, classes, instances, values, unfoldings, etc (henceforth
-referred to as ``entities''), available from @M@. These are just
-trees in the GHCI heap. References from other modules to these
-entities is direct -- when you have a @TyCon@ in your hand, you really
-have a pointer directly to the @TyCon@ structure in the defining module,
-rather than some kind of index into a global symbol table. So there
-is a global symbol table, but it has a distributed (sphagetti-like?)
-nature.
-
-This gives fast and convenient access to tycon, class, instance,
-etc, information. But because there are no levels of indirection,
-there's a problem when we replace @M@ with an updated version of @M@.
-We then need to find all references to entities in the old @M@'s
-sphagetti, and replace them with pointers to the new @M@'s sphagetti.
-This problem motivates a large part of the design.
-
-
-
-\subsection{Implementing incremental recompilation -- simple version}
-Given the following module graph
-\begin{verbatim}
- D
- / \
- / \
- B C
- \ /
- \ /
- A
-\end{verbatim}
-(@D@ imports @B@ and @C@, @B@ imports @A@, @C@ imports @A@) the aim is to do the
-least possible amount of compilation to bring @D@ back up to date. The
-simplest scheme we can think of is:
-\begin{itemize}
-\item {\bf Downsweep}:
- starting with @D@, re-establish what the current module graph is
- (it might have changed since last time). This means getting a
- @ModuleSummary@ of @D@. The summary can be quickly generated,
- contains @D@'s import lists, and gives some way of knowing whether
- @D@'s source has changed since the last time it was summarised.
-
- Transitively follow summaries from @D@, thereby establishing the
- module graph.
-\item
- Remove from the global symbol table (the @FiniteMap@ @ModuleName@
- @ModuleDetails@) the upwards closure of all modules in this package
- which are out-of-date with respect to their previous versions. Also
- remove all modules no longer reachable from @D@.
-\item {\bf Upsweep}:
- Starting at the lowest point in the still-in-date module graph,
- start compiling upwards, towards @D@. At each module, call
- @compile@, passing it a @FiniteMap@ @ModuleName@ @ModuleDetails@,
- and getting a new @ModuleDetails@ for the module, which is added to
- the map.
-
- When compiling a module, the compiler must be able to know which
- entries in the map are for modules in its strict downwards closure,
- and which aren't, so that it can manufacture the instance
- environment correctly (as union of instances in its downwards
- closure).
-\item
- Once @D@ has been compiled, invoke some kind of linking phase
- if batch compilation. For interactive use, can either do it all
- at the end, or as you go along.
-\end{itemize}
-In this simple world, recompilation visits the upwards closure of
-all changed modules. That means when a module @M@ is recompiled,
-we can be sure no-one has any references to entities in the old @M@,
-because modules importing @M@ will have already been removed from the
-top-level finite map in the second step above.
-
-The upshot is that we don't need to worry about updating links to @M@ in
-the global symbol table -- there shouldn't be any to update.
-\ToDo{What about mutually recursive modules?}
-
-CM will happily chase through module interfaces in other packages in
-the downsweep. But it will only process modules in this package
-during the upsweep. So it assumes that modules in other packages
-never become out of date. This is a design decision -- we could have
-decided otherwise.
-
-In fact we go further, and require other packages to be compiled,
-i.e. to consist of a collection of interface files, and one or more
-source files. CM will never apply @compile@ to a foreign package
-module, so there's no way a package can be built on the fly from source.
-
-We require @compile@ to cache foreign package interfaces it reads, so
-that subsequent uses don't have to re-read them. The cache never
-becomes out of date, since we've assumed that the source of foreign
-packages doesn't change during the course of a session (run of GHCI).
-As well as caching interfaces, @compile@ must cache, in some sense,
-the linkable code for modules. In batch compilation this might simply
-mean remembering the names of object files to link, whereas in
-interactive mode @compile@ probably needs to load object code into
-memory in preparation for in-memory linking.
-
-Important signatures for this simple scheme are:
-\begin{verbatim}
- finder :: ModuleName -> ModLocation
-
- summarise :: ModLocation -> IO ModSummary
-
- compile :: ModSummary
- -> FM ModName ModDetails
- -> IO CompileResult
-
- data CompileResult = CompOK ModDetails
- | CompErr [ErrMsg]
-
- link :: [ModLocation] -> [PackageLocation] -> IO Bool -- linked ok?
-\end{verbatim}
-
-
-\subsection{Implementing incremental recompilation -- clever version}
-
-So far, our upsweep, which is the computationally expensive bit,
-recompiles a module if either its source is out of date, or it
-imports a module which has been recompiled. Sometimes we know
-we can do better than this:
-\begin{verbatim}
- module B where module A
- import A ( f ) {-# NOINLINE f #-}
- ... f ... f x = x + 42
-\end{verbatim}
-If the definition of @f@ is changed to @f x = x + 43@, the simple
-upsweep would recompile @B@ unnecessarily. We would like to detect
-this situation and avoid propagating recompilation all the way to the
-top. There are two parts to this: detecting when a module doesn't
-need recompilation, and managing inter-module references in the
-global symbol table.
-
-\subsubsection*{Detecting when a module doesn't need recompilation}
-
-To do this, we introduce a new concept: the @ModuleIFace@. This is
-effectively an in-memory interface file. References to entities in
-other modules are done via strings, rather than being pointers
-directly to those entities. Recall that, by comparison,
-@ModuleDetails@ do contain pointers directly to the entities they
-refer to. So a @ModuleIFace@ is not part of the global symbol table.
-
-As before, compiling a module produces a @ModuleDetails@ (inside the
-@CompileResult@), but it also produces a @ModuleIFace@. The latter
-records, amongst things, the version numbers of all imported entities
-needed for the compilation of that module. @compile@ optionally also
-takes the old @ModuleIFace@ as input during compilation:
-\begin{verbatim}
- data CompileResult = CompOK ModDetails ModIFace
- | CompErr [ErrMsg]
-
- compile :: ModSummary
- -> FM ModName ModDetails
- -> Maybe ModuleIFace
- -> IO CompileResult
-\end{verbatim}
-Now, if the @ModuleSummary@ indicates this module's source hasn't
-changed, we only need to recompile it if something it depends on has
-changed. @compile@ can detect this by inspecting the imported entity
-version numbers in the module's old @ModuleIFace@, and comparing them
-with the version numbers from the entities in the modules being
-imported. If they are all the same, nothing it depends on has
-changed, so there's no point in recompiling.
-
-\subsubsection*{Managing inter-module references in the global symbol table}
-
-In the above example with @A@, @B@ and @f@, the specified change to @f@ would
-require @A@ but not @B@ to be recompiled. That generates a new
-@ModuleDetails@ for @A@. Problem is, if we leave @B@'s @ModuleDetails@
-unchanged, they continue to refer (directly) to the @f@ in @A@'s old
-@ModuleDetails@. This is not good, especially if equality between
-entities is implemented using pointer equality.
-
-One solution is to throw away @B@'s @ModuleDetails@ and recompile @B@.
-But this is precisely what we're trying to avoid, as it's expensive.
-Instead, a cheaper mechanism achieves the same thing: recreate @B@'s
-details directly from the old @ModuleIFace@. The @ModuleIFace@ will
-(textually) mention @f@; @compile@ can then find a pointer to the
-up-to-date global symbol table entry for @f@, and place that pointer
-in @B@'s @ModuleDetails@. The @ModuleDetails@ are, therefore,
-regenerated just by a quick lookup pass over the module's former
-@ModuleIFace@. All this applies, of course, only when @compile@ has
-concluded it doesn't need to recompile @B@.
-
-Now @compile@'s signature becomes a little clearer. @compile@ has to
-recompile the module, generating a fresh @ModuleDetails@ and
-@ModuleIFace@, if any of the following hold:
-\begin{itemize}
-\item
- The old @ModuleIFace@ wasn't supplied, for some reason (perhaps
- we've never compiled this module before?)
-\item
- The module's source has changed.
-\item
- The module's source hasn't changed, but inspection of @ModuleIFaces@
- for this and its imports indicates that an imported entity has
- changed.
-\end{itemize}
-If none of those are true, we're in luck: quickly knock up a new
-@ModuleDetails@ from the old @ModuleIFace@, and return them both.
-
-As a result, the upsweep still visits all modules in the upwards
-closure of those whose sources have changed. However, at some point
-we hopefully make a transition from generating new @ModuleDetails@ the
-expensive way (recompilation) to a cheap way (recycling old
-@ModuleIFaces@). Either way, all modules still get new
-@ModuleDetails@, so the global symbol table is correctly
-reconstructed.
-
-
-\subsection{How linking works, roughly}
-
-When @compile@ translates a module, it produces a @ModuleDetails@,
-@ModuleIFace@ and a @Linkable@. The @Linkable@ contains the
-translated but un-linked code for the module. And when @compile@
-ventures into an interface in package it hasn't seen so far, it
-copies the package's object code into memory, producing one or more
-@Linkable@s. CM keeps track of these linkables.
-
-Once all modules have been @compile@d, CM invokes @link@, supplying
-the all the @Linkable@s it knows about. If @compile@ had also been
-linking incrementally as it went along, @link@ doesn't have to do
-anything. On the other hand, @compile@ could choose not to be
-incremental, and leave @link@ to do all the work.
-
-@Linkable@s are opaque to CM. For batch compilation, a @Linkable@
-can record just the name of an object file, DLL, archive, or whatever,
-in which case the CM's call to @link@ supplies exactly the set of
-file names to be linked. @link@ can pass these verbatim to the
-standard system linker.
-
-
-
-
-%%-----------------------------------------------------------------%%
-\section{Ancient stuff}
-\subsubsection*{Should be selectively merged into ``Background ideas''}
-
-\subsection{Overall}
-Top level structure is:
-\begin{itemize}
-\item The Compilation Manager (CM) calculates and maintains module
- dependencies, and knows how create up-to-date object or bytecode
- for a given module. In doing so it may need to recompile
- arbitrary other modules, based on its knowledge of the module
- dependencies.
-\item On top of the CM are the ``user-level'' services. We envisage
- both a HEP-like interface, for interactive use, and an
- @hmake@ style batch compiler facility.
-\item The CM only deals with inter-module issues. It knows nothing
- about how to recompile an individual module, nor where the compiled
- result for a module lives, nor how to tell if
- a module is up to date, nor how to find the dependencies of a module.
- Instead, these services are supplied abstractly to CM via a
- @Compiler@ record. To a first approximation, a @Compiler@
- contains
- the same functionality as @hsc@ has had until now -- the ability to
- translate a single Haskell module to C/assembly/object/bytecode.
-
- Different clients of CM (HEP vs @hmake@) may supply different
- @Compiler@s, since they need slightly different behaviours.
- Specifically, HEP needs a @Compiler@ which creates bytecode
- in memory, and knows how to link it, whereas @hmake@ wants
- the traditional behaviour of emitting assembly code to disk,
- and making no attempt at linkage.
-\end{itemize}
-
-\subsection{Open questions}
-\begin{itemize}
-\item
- Error reporting from @open@ and @compile@.
-\item
- Instance environment management
-\item
- We probably need to make interface files say what
- packages they depend on (so that we can figure out
- which packages to load/link).
-\item
- CM is parameterised both by the client uses and the @Compiler@
- supplied. But it doesn't make sense to have a HEP-style client
- attached to a @hmake@-style @Compiler@. So, really, the
- parameterising entity should contain both aspects, not just the
- current @Compiler@ contents.
-\end{itemize}
-
-\subsection{Assumptions}
-
-\begin{itemize}
-\item Packages other than the "current" one are assumed to be
- already compiled.
-\item
- The "current" package is usually "MAIN",
- but we can set it with a command-line flag.
- One invocation of ghci has only one "current" package.
-\item
- Packages are not mutually recursive
-\item
- All the object code for a package P is in libP.a or libP.dll
-\end{itemize}
-
-\subsection{Stuff we need to be able to do}
-\begin{itemize}
-\item Create the environment in which a module has been translated,
- so that interactive queries can be satisfied as if ``in'' that
- module.
-\end{itemize}
-
-%%-----------------------------------------------------------------%%
-\section{The Compilation Manager}
-
-CM (@compilationManager@) is a functor, thus:
-\begin{verbatim}
-compilationManager :: Compiler -> IO HEP -- IO so that it can create
- -- global vars (IORefs)
-
-data HEP = HEP {
- load :: ModuleName -> IO (),
- compileString :: ModuleName -> String -> IO HValue,
- ....
- }
-
-newCompiler :: IO Compiler -- ??? this is a peer of compilationManager?
-
-run :: HValue -> IO () -- Run an HValue of type IO ()
- -- In HEP?
-\end{verbatim}
-
-@load@ is the central action of CM: its job is to bring a module and
-all its descendents into an executable state, by doing the following:
-\begin{enumerate}
-\item
- Use @summarise@ to descend the module hierarchy, starting from the
- nominated root, creating @ModuleSummary@s, and
- building a map @ModuleName@ @->@ @ModuleSummary@. @summarise@
- expects to be passed absolute paths to files. Use @finder@ to
- convert module names to file paths.
-\item
- Topologically sort the map,
- using dependency info in the @ModuleSummary@s.
-\item
- Clean up the symbol table by deleting the upward closure of
- changed modules.
-\item
- Working bottom to top, call @compile@ on the upward closure of
- all modules whose source has changed. A module's source has
- changed when @sourceHasChanged@ indicates there is a difference
- between old and new summaries for the module. Update the running
- @FiniteMap@ @ModuleName@ @ModuleDetails@ with the new details
- for this module. Ditto for the running
- @FiniteMap@ @ModuleName@ @ModuleIFace@.
-\item
- Call @compileDone@ to signify that we've reached the top, so
- that the batch system can now link.
-\end{enumerate}
-
-
-%%-----------------------------------------------------------------%%
-\section{A compiler}
-
-Most of the system's complexity is hidden inside the functions
-supplied in the @Compiler@ record:
-\begin{verbatim}
-data Compiler = Compiler {
-
- finder :: PackageConf -> [Path] -> IO (ModuleName -> ModuleLocation)
-
- summarise :: ModuleLocation -> IO ModuleSummary
-
- compile :: ModuleSummary
- -> Maybe ModuleIFace
- -> FiniteMap ModuleName ModuleDetails
- -> IO CompileResult
-
- compileDone :: IO ()
- compileStarting :: IO () -- still needed? I don't think so.
- }
-
-type ModuleName = String (or some such)
-type Path = String -- an absolute file name
-\end{verbatim}
-
-\subsection{The module \mbox{\tt finder}}
-The @finder@, given a package configuration file and a list of
-directories to look in, will map module names to @ModuleLocation@s,
-in which the @Path@s are filenames, probably with an absolute path
-to them.
-\begin{verbatim}
-data ModuleLocation = SourceOnly Path -- .hs
- | ObjectCode Path Path -- .o & .hi
- | InPackage Path -- .hi
-\end{verbatim}
-@SourceOnly@ and @ObjectCode@ are unremarkable. For sanity,
-we require that a module's object and interface be in the same
-directory. @InPackage@ indicates that the module is in a
-different package.
-
-@Module@ values -- perhaps all @Name@ish things -- contain the name of
-their package. That's so that
-\begin{itemize}
-\item Correct code can be generated for in-DLL vs out-of-DLL refs.
-\item We don't have version number dependencies for symbols
- imported from different packages.
-\end{itemize}
-
-Somehow or other, it will be possible to know all the packages
-required, so that the for the linker can load them.
-We could detect package dependencies by recording them in the
-@compile@r's @ModuleIFace@ cache, and with that and the
-package config info, figure out the complete set of packages
-to link. Or look at the command line args on startup.
-
-\ToDo{Need some way to tell incremental linkers about packages,
- since in general we'll need to load and link them before
- linking any modules in the current package.}
-
-
-\subsection{The module \mbox{\tt summarise}r}
-Given a filename of a module (\ToDo{presumably source or iface}),
-create a summary of it. A @ModuleSummary@ should contain only enough
-information for CM to construct an up-to-date picture of the
-dependency graph. Rather than expose CM to details of timestamps,
-etc, @summarise@ merely provides an up-to-date summary of any module.
-CM can extract the list of dependencies from a @ModuleSummary@, but
-other than that has no idea what's inside it.
-\begin{verbatim}
-data ModuleSummary = ... (abstract) ...
-
-depsFromSummary :: ModuleSummary -> [ModuleName] -- module names imported
-sourceHasChanged :: ModuleSummary -> ModuleSummary -> Bool
-\end{verbatim}
-@summarise@ is intended to be fast -- a @stat@ of the source or
-interface to see if it has changed, and, if so, a quick semi-parse to
-determine the new imports.
-
-\subsection{The module \mbox{\tt compile}r}
-@compile@ traffics in @ModuleIFace@s and @ModuleDetails@.
-
-A @ModuleIFace@ is an in-memory representation of the contents of an
-interface file, including version numbers, unfoldings and pragmas, and
-the linkable code for the module. @ModuleIFace@s are un-renamed,
-using @HsSym@/@RdrNames@ rather than (globally distinct) @Names@.
-
-@ModuleDetails@, by contrast, is an in-memory representation of the
-static environment created by compiling a module. It is phrased in
-terms of post-renaming @Names@, @TyCon@s, etc, so it's basically a
-renamed-to-global-uniqueness rendition of a @ModuleIFace@.
-
-In an interactive session, we'll want to be able to evaluate
-expressions as if they had been compiled in the scope of some
-specified module. This means that the @ModuleDetails@ must contain
-the type of everything defined in the module, rather than just the
-types of exported stuff. As a consequence, @ModuleIFace@ must also
-contain the type of everything, because it should always be possible
-to generate a module's @ModuleDetails@ from its @ModuleIFace@.
-
-CM maintains two mappings, one from @ModuleName@s to @ModuleIFace@s,
-the other from @ModuleName@s to @ModuleDetail@s. It passes the former
-to each call of @compile@. This is used to supply information about
-modules compiled prior to this one (lower down in the graph). The
-returned @CompileResult@ supplies a new @ModuleDetails@ for the module
-if compilation succeeded, and CM adds this to the mapping. The
-@CompileResult@ also supplies a new @ModuleIFace@, which is either the
-same as that supplied to @compile@, if @compile@ decided not to
-retranslate the module, or is the result of a fresh translation (from
-source). So these mappings are an explicitly-passed-around part of
-the global system state.
-
-@compile@ may also {\em optionally} also accumulate @ModuleIFace@s for
-modules in different packages -- that is, interfaces which we read,
-but never attempt to recompile source for. Such interfaces, being
-from foreign packages, never change, so @compile@ can accumulate them
-in perpetuity in a private global variable. Indeed, a major motivator
-of this design is to facilitate this caching of interface files,
-reading of which is a serious bottleneck for the current compiler.
-
-When CM restarts compilation down at the bottom of the module graph,
-it first needs to throw away all \ToDo{all?} @ModuleDetails@ in the
-upward closure of the out-of-date modules. So @ModuleDetails@ don't
-persist across recompilations. But @ModuleIFace@s do, since they
-are conceptually equivalent to interface files.
-
-
-\subsubsection*{What @compile@ returns}
-@compile@ returns a @CompileResult@ to CM.
-Note that the @compile@'s foreign-package interface cache can
-become augmented even as a result of reading interfaces for a
-compilation attempt which ultimately fails, although it will not be
-augmented with a new @ModuleIFace@ for the failed module.
-\begin{verbatim}
--- CompileResult is not abstract to the Compilation Manager
-data CompileResult
- = CompOK ModuleIFace
- ModuleDetails -- compiled ok, here are new details
- -- and new iface
-
- | CompErr [SDoc] -- compilation gave errors
-
- | NoChange -- no change required, meaning:
- -- exports, unfoldings, strictness, etc,
- -- unchanged, and executable code unchanged
-\end{verbatim}
-
-
-
-\subsubsection*{Re-establishing local-to-global name mappings}
-Consider
-\begin{verbatim}
-module Upper where module Lower ( f ) where
-import Lower ( f ) f = ...
-g = ... f ...
-\end{verbatim}
-When @Lower@ is first compiled, @f@ is allocated a @Unique@
-(presumably inside an @Id@ or @Name@?). When @Upper@ is then
-compiled, its reference to @f@ is attached directly to the
-@Id@ created when compiling @Lower@.
-
-If the definition of @f@ is now changed, but not the type,
-unfolding, strictness, or any other thing which affects the way
-it should be called, we will have to recompile @Lower@, but not
-@Upper@. This creates a problem -- @g@ will then refer to the
-the old @Id@ for @f@, not the new one. This may or may not
-matter, but it seems safer to ensure that all @Unique@-based
-references into child modules are always up to date.
-
-So @compile@ recreates the @ModuleDetails@ for @Upper@ from
-the @ModuleIFace@ of @Upper@ and the @ModuleDetails@ of @Lower@.
-
-The rule is: if a module is up to date with respect to its
-source, but a child @C@ has changed, then either:
-\begin{itemize}
-\item On examination of the version numbers in @C@'s
- interface/@ModuleIFace@ that we used last time, we discover that
- an @Id@/@TyCon@/class/instance we depend on has changed. So
- we need to retranslate the module from its source, generating
- a new @ModuleIFace@ and @ModuleDetails@.
-\item Or: there's nothing in @C@'s interface that we depend on.
- So we quickly recreate a new @ModuleDetails@ from the existing
- @ModuleIFace@, creating fresh links to the new @Unique@-world
- entities in @C@'s new @ModuleDetails@.
-\end{itemize}
-
-Upshot: we need to redo @compile@ on all modules all the way up,
-rather than just the ones that need retranslation. However, we hope
-that most modules won't need retranslation -- just regeneration of the
-@ModuleDetails@ from the @ModuleIFace@. In effect, the @ModuleIFace@
-is a quickly-compilable representation of the module's contents, just
-enough to create the @ModuleDetails@.
-
-\ToDo{Is there anything in @ModuleDetails@ which can't be
- recreated from @ModuleIFace@ ?}
-
-So the @ModuleIFace@s persist across calls to @HEP.load@, whereas
-@ModuleDetails@ are reconstructed on every compilation pass. This
-means that @ModuleIFace@s have the same lifetime as the byte/object
-code, and so should somehow contain their code.
-
-The behind-the-scenes @ModuleIFace@ cache has some kind of holding-pen
-arrangement, to lazify the copying-out of stuff from it, and thus to
-minimise redundant interface reading. \ToDo{Burble burble. More
-details.}.
-
-When CM starts working back up the module graph with @compile@, it
-needs to remove from the travelling @FiniteMap@ @ModuleName@
-@ModuleDetails@ the details for all modules in the upward closure of
-the compilation start points. However, since we're going to visit
-precisely those modules and no others on the way back up, we might as
-well just zap them the old @ModuleDetails@ incrementally. This does
-mean that the @FiniteMap@ @ModuleName@ @ModuleDetails@ will be
-inconsistent until we reach the top.
-
-In interactive mode, each @compile@ call on a module for which no
-object code is available, or for which it is out of date wrt source,
-emit bytecode into memory, update the resulting @ModuleIFace@ with the
-address of the bytecode image, and link the image.
-
-In batch mode, emit assembly or object code onto disk. Record
-somewhere \ToDo{where?} that this object file needs to go into the
-final link.
-
-When we reach the top, @compileDone@ is called, to signify that batch
-linking can now proceed, if need be.
-
-Modules in other packages never get a @ModuleIFace@ or @ModuleDetails@
-entry in CM's maps -- those maps are only for modules in this package.
-As previously mentioned, @compile@ may optionally cache @ModuleIFace@s
-for foreign package modules. When reading such an interface, we don't
-need to read the version info for individual symbols, since foreign
-packages are assumed static.
-
-\subsubsection*{What's in a \mbox{\tt ModuleIFace}?}
-
-Current interface file contents?
-
-
-\subsubsection*{What's in a \mbox{\tt ModuleDetails}?}
-
-There is no global symbol table @:: Name -> ???@. To look up a
-@Name@, first extract the @ModuleName@ from it, look that up in
-the passed-in @FiniteMap@ @ModuleName@ @ModuleDetails@,
-and finally look in the relevant @Env@.
-
-\ToDo{Do we still have the @HoldingPen@, or is it now composed from
-per-module bits too?}
-\begin{verbatim}
-data ModuleDetails = ModuleDetails {
-
- moduleExports :: what it exports (Names)
- -- roughly a subset of the .hi file contents
-
- moduleEnv :: RdrName -> Name
- -- maps top-level entities in this module to
- -- globally distinct (Uniq-ified) Names
-
- moduleDefs :: Bag Name -- All the things in the global symbol table
- -- defined by this module
-
- package :: Package -- what package am I in?
-
- lastCompile :: Date -- of last compilation
-
- instEnv :: InstEnv -- local inst env
- typeEnv :: Name -> TyThing -- local tycon env?
- }
-
--- A (globally unique) symbol table entry. Note that Ids contain
--- unfoldings.
-data TyThing = AClass Class
- | ATyCon TyCon
- | AnId Id
-\end{verbatim}
-What's the stuff in @ModuleDetails@ used for?
-\begin{itemize}
-\item @moduleExports@ so that the stuff which is visible from outside
- the module can be calculated.
-\item @moduleEnv@: \ToDo{umm err}
-\item @moduleDefs@: one reason we want this is so that we can nuke the
- global symbol table contribs from this module when it leaves the
- system. \ToDo{except ... we don't have a global symbol table any
- more.}
-\item @package@: we will need to chase arbitrarily deep into the
- interfaces of other packages. Of course we don't want to
- recompile those, but as we've read their interfaces, we may
- as well cache that info. So @package@ indicates whether this
- module is in the default package, or, if not, which it is in.
-
- Also, when we come to linking, we'll need to know which
- packages are demanded, so we know to load their objects.
-
-\item @lastCompile@: When the module was last compiled. If the
- source is older than that, then a recompilation can only be
- required if children have changed.
-\item @typeEnv@: obvious??
-\item @instEnv@: the instances contributed by this module only. The
- Report allegedly says that when a module is translated, the
- available
- instance env is all the instances in the downward closure of
- itself in the module graph.
-
- We choose to use this simple representation -- each module
- holds just its own instances -- and do the naive thing when
- creating an inst env for compilation with. If this turns out
- to be a performance problem we'll revisit the design.
-\end{itemize}
-
-
-
-%%-----------------------------------------------------------------%%
-\section{Misc text looking for a home}
-
-\subsection*{Linking}
-
-\ToDo{All this linking stuff is now bogus.}
-
-There's an abstract @LinkState@, which is threaded through the linkery
-bits. CM can call @addpkgs@ to notify the linker of packages
-required, and it can call @addmods@ to announce modules which need to
-be linked. Finally, CM calls @endlink@, after which an executable
-image should be ready. The linker may link incrementally, during each
-call of @addpkgs@ and @addmods@, or it can just store up names and do
-all the linking when @endlink@ is called.
-
-In order that incremental linking is possible, CM should specify
-packages and module groups in dependency order, ie, from the bottom up.
-
-\subsection*{In-memory linking of bytecode}
-When being HEP-like, @compile@ will translate sources to bytecodes
-in memory, with all the bytecode for a module as a contiguous lump
-outside the heap. It needs to communicate the addresses of these
-lumps to the linker. The linker also needs to know whether a
-given module is available as in-memory bytecode, or whether it
-needs to load machine code from a file.
-
-I guess @LinkState@ needs to map module names to base addresses
-of their loaded images, + the nature of the image, + whether or not
-the image has been linked.
-
-\subsection*{On disk linking of object code, to give an executable}
-The @LinkState@ in this case is just a list of module and package
-names, which @addpkgs@ and @addmods@ add to. The final @endlink@
-call can invoke the system linker.
-
-\subsection{Finding out about packages, dependencies, and auxiliary
- objects}
-
-Ask the @packages.conf@ file that lives with the driver at the mo.
-
-\ToDo{policy about upward closure?}
-
-
-
-\ToDo{record story about how in memory linking is done.}
-
-\ToDo{linker start/stop/initialisation/persistence. Need to
- say more about @LinkState@.}
-
-
-\end{document}
-
-
projects / ghc-hetmet.git / blobdiff