% % (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 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 a package interface to PIT doesn't make it directly usable to @compile@, because it first needs to be wired (renamed + typechecked) into the spaghetti 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 GHC.Tc.Utils.Env 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 (spaghetti-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 spaghetti, and replace them with pointers to the new @M@'s spaghetti. 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}