Changes between Version 25 and Version 26 of GhciDebugger

Apr 25, 2007 7:40:12 PM (8 years ago)

Clean up and include the details on the latest :print changes


  • GhciDebugger

    v25 v26  
    1616= The closure viewer =
    17 The closure viewer functionality is provided by the following function at the GHC module:
     17The closure viewer functionality is provided by the following function in the GHC API:
    1919obtainTerm :: Session -> Bool -> Id -> IO (Maybe Term)
    4747=== DataCon recovery ===
    48 The closure viewer obtains the heap address of a Haskell value, find out the address of its associated info table, and trace back to the DataCon corresponding to this info table. This is possible because the ghc runtime allocates a static info table for each and every datacon, so all we have to do is extend the linker with a dictionary relating the static info table addresses to a DataCon name.
    49 Moreover, the ghci linker can load interpreted code containing new `data` or `newtype` declarations. So the dynamic linker code is extended in the same way. To sum up:
    50  * `linker.c` has a new hashtable for datacons.
    51  * `ghci/Linker.hs` has been extended in a similar way. The Persistent Link State datatype now includes a datacons environment. At `linkExpr` and `dynLinkBCOs` the environment is extended with _any_ new datacons witnessed.
    52    * Since this scheme makes no distinction between statically and dynamically loaded info tables a lot of redundancy goes into this environment, maybe it's worth to fix this.
     48UPDATE: This is now done differently. See ticket #1085
    54 Two new primitive ops have been created which allow to obtain the address of a closure info table and to obtain the closure payload (i.e. if it is a value, the arguments of the datacon).
    55 {{{
    56 infoPtr# :: a -> Addr#
    57 closurePayload# :: a -> (# Array# b, ByteArr# #)
    58 }}}
    59 The use of these primitives is encapsulated in the `RtClosureInspect` module, which provides:
    60 {{{
    61 getClosureType  :: a -> IO ClosureType
    62 getInfoTablePtr :: a -> Ptr StgInfoTable
    63 getClosureData  :: a -> IO Closure
    65 data Closure = Closure { tipe         :: ClosureType
    66                        , infoTable    :: StgInfoTable
    67                        , ptrs         :: Array Int HValue
    68                        , nonPtrs      :: ByteArray#
    69                        }
    71 data ClosureType = Constr
    72                  | Fun
    73                  | Thunk Int
    74                  | ThunkSelector
    75                  | Blackhole
    76                  | AP
    77                  | PAP
    78                  | Indirection Int
    79                  | Other Int
    80  deriving (Show, Eq)
    81 }}}
    83 The implementation of the datacon recovery stuff is scattered around:
    84 {{{
    85 Linker.recoverDataCon :: a -> TcM Name
    86  |- recoverDCInDynEnv :: a -> IO (Maybe Name)
    87  |- recoverDCInRTS    :: a -> TcM Name
    88     |- ObjLink.lookupDataCon :: Ptr StgInfoTable -> IO (Maybe String)
    89 }}}
    90 First we must make sure that we are dealing with a whnf value (i.e. a Constr), as opposed to a thunk, fun, indirection, etc. This information is retrieved from the very own info table (StgInfoTable comes with a Storable instance, defined at ByteCodeItbls). From here on I will use simply constr to refer to a Constr closure.
    92 Once we have the ability to recover the datacon of a constr and thus its (possibly polymorphic) type, we can construct its tree representation. The payload of a closure is an ordered set of pointers and non pointers (words). For a Constr closure, the non pointers correspond to leafs of the tree, primitive unboxed values, the pointers being the so-called subTerms, references to other closures.
     50(If for some reason you want to check the original solution, browse the history for this wiki page.)
    9452=== Recovering non-pointers ===
    112 === Type reconstruction ===
     70=== Type Reconstruction ===
    11371Type reconstruction is the process of recovering the full type of a closure which has a polymorphic dataCon.
    127 This can be quite tricky to solve if done in full generality, as it amounts to unification modulo a set of equations which is known to be undecidible. The closure viewer uses the simpler trick of scanning every constraint lhs for newtypes and adjusting the rhs correspondingly. This simple trick seems to do it (see `congruenceNewtypes` at  [[GhcFile(compiler/ghci/RtClosureInspect.hs)]]).
     85This can be quite tricky to solve if done in full generality, as it amounts to unification modulo a set of equations which is known to be undecidible. The closure viewer uses a set of typing rules to get around this. The details are in the paper.
     87The current implementation follows the paper in everything except one thing. When doing type reconstruction for large structures, things can get very slow. For instance, :print'ing a list with 50.000 integers (which does type reconstruction) means doing around 50.000 unification steps, which takes around 4 minutes in my box. Of course, of those 50.000 we only need two. Thus the algorithm has been modified to use matching when unification is not needed. When is that ? When a type is monomorphic. This brings down the time to a few seconds, since the list structure still needs to be walked in order to construct the term. (could this be done more lazily? anyway, it is not really a problem in practice).
    130 === About handling suspensions in the interactive environment ===
    131 Often it is not possible to reconstruct the most concrete type, because children of a value are suspended. When this happens we have a value with polymorphic type, and this is a problem for two reasons. First, for the user, who cannot interact with the value in the usual way. Second, for ghci, because it does not deal well with tyvars in the type of values.
    133 Ideally, we want to lift this restriction on ghci some day. For now, the tyvars are instantiated to a family of dummy types, indexed by kind arity, which live in GHC.Base: `Unknown`, `Unknown1`,`Unknown2`, etc.
     89=== Handling suspensions ===
    13591The interactive ui uses `obtainTerm` from the ghc-api, which lives at  [[GhcFile(compiler/ghci/RtClosureInspect.hs)]], to implement the :print and :sprint command. The difference is that :print, additionally, binds suspended values.
    13692Thus, suspensions inside semievaluated terms are bound by `:print` to _t,,xx,, names in the interactive environment, available for the user.
     93Most of this happens at `pprintClosureCommand` in  [[GhcFile(compiler/ghci/Debugger.hs)]].
    138 This is done at `pprintClosure`in  [[GhcFile(compiler/ghci/Debugger.hs)]], which takes responsibility of instantiating tyvars with  members the `GHC.Base.Unknown` family. A  an associated Show instance is provided that instructs the user to `seq` them to recover the type.
    140 There are two quirks with the current solution:
    141  * It does not remember previous bindings. Two consecutive uses of `:print` will generate two separate bindings for the same thing, generating redundancy and potential confusion. But...
    142  * since type reconstruction (for polymorphic/untyped things) can eventually happen whenever the suspensions are forced, it is necessary to use `:print` again to obtain a binding with the refined type
    143    * It is a future work to make ghci do this type reconstruction implicitly on the existing, polymorphic bindings. This would be ''nice'' for the _t,,xx,, things, but even nicer for the local bindings in the context of a breakpoint.
     95Quirks with the current solution:
     96 * It does not remember previous bindings. Two consecutive uses of `:print` will generate two separate bindings for the same thing, generating redundancy and potential confusion.
    14598=== Type Refinement ===
    146 `InteractiveUI.pprintClosure` has some smartness in to update the type of a value as it is refined by forcing evaluation. As an example, look at the following (allegedly extreme) debugging session snippet:
     99Often it is not possible to reconstruct the most concrete type, because children of a value are suspended. When this happens we have a value with polymorphic type, and this is a problem for two reasons. First, for the user, who cannot interact with the value in the usual way. Second, for ghci, because it does not deal well with tyvars in the type of values.
     101Incompletely recovered types are instantiated with "Skolem" tyvars (ask the Simons) and GHC has been modified so that they will not be affected by Haskell 98 defaulting rules. This is in order to stop them from defaulting to ()  in GHCi and causing weird things (or eventually segfaults).
     103Type refinement happens when, after some forcing of closures by the user, the type reconstruction scheme is able to compute a more concrete type. In this case, the :print command updates the type of the binding in the environment with the new information. Not only that, it updates all the types in the environment with the computed substitution.
     105The ultimate effect of this solution is that, if there are two or more bindings in the environment whose types are related, the substitution computed after some type reconstruction step will be applied to all of them. For instance, if we are debugging a `map` function:
     108map :: (a -> b) -> [a]->[b]
     109map f x = ...
     112recovering the type of `x` (how? after forcing and using :print, see the next section)
     113will cause the type of `f` to be updated in its first argument too.
     115This is a summary of how things go. The user invokes :print on some binding and `pprintClosureCommand` does:
     116 - use `obtainTerm` to construct the term. This computes the most concrete possible type.
     117 - unify the old and new types to compute a substitution.
     118 - instantiate the range of the substitution with skolem tyvars
     119 - apply the substitution to all the types in the environment, including the old type
     121One more detail, newtypes need to be flattened before doing the unification step;
     122type reconstruction may not have bee able to recover the newtype representation.
     124==== Example ====
     125This is an example of type reconstruction/refinement
     126in an (allegedly extreme) debugging session snippet:
     129TODO: Update this example
    149131Local bindings in scope:
    150132  r :: a
    188170Note how the type of the binding `r` gets updated during the debugging session.
    190 This piece of smartness is actually quite dumb and in need of improvement. The criteria to decide whether a new type is more specific than the previous is to unify both and check that the substitution:
    191  * Binds at least one vars from the old type to some concrete type (i.e. no vars to vars bindings)
    192  * Binds no vars from the new type
    194 I just noticed that this won't detect refinements as: `Either a b` goes to `Either a a`
    196 There is probably an easy to formulate optimum criteria, but I can't figure it out for now :(
    198 One more thing, newtypes need to be flattened before doing the unification; type reconstruction may not be able to recover the newtype representation.
    200175=== Pretty printing of terms ===
    207182= Breakpoints =
     183UPDATE: This is now done differently. See NewGhciDebugger
    209 == `breakpoint`  Implementation ==
    210 When compiling to bytecodes, breakpoints are desugared to 'fake' jump functions, i.e. they are not defined anywhere, later in the interactive environment we link them to something:
    211 {{{
    212 breakpoint => breakpointJump
    213 breakpointCond => breakpointCondJump
    214 breakpointAuto => breakpointAutoJump
    215 }}}
    216 The types would be:
    217 {{{
    218 data Locals = forall a. Locals a
    220 breakpointAutoJump, breakpointJump ::
    221                     Int                         -- Address of a StablePtr containing the Ids
    222                  -> [Locals]                    -- Local bindings list
    223                  -> (String, String, Int)       -- Package, Module and site number
    224                  -> String                      -- Location message (filename + srcSpan)
    225                  -> b -> b                 
    226 breakpointCondJump :: Int -> [Locals] -> (String,String,Int) -> String -> Bool -> b -> b
    227 }}}
    228 They get filled with the pointer to the ids in scope, their values, the site, a message, and the wrapped value in the desugarer. Everything served with the right amounts of unsafeCoerce sauce and TyApp dressing to make sure it core-lints.
    230 This transformation is loosely formalized in GhciDebugger/BreakpointJump
    232 The site number is relevant only for 'auto' breakpoints, explained later. For the other two types of breakpoints its value should be 0.
    234 The desugarer monad has been extended with an OccEnv of Ids to track the bindings in scope. Of course this environment thing is probably too ad-hoc to use it for anything else. The monad also carries a mutable table of breakpoint sites for the current module. This table is propagated to the ModGuts.
    236 === Default HValues for the Jump functions ===
    237 The dynamic linker has been modified so that it won't panic if one of the jump functions fails to resolve.
    238 Now if the dynamic linker fails to find a HValue for a Name, before looking for a static symbol it will ask
    239 {{{
    240 DsBreakpoint.lookupBogusBreakpointVal :: Name -> Maybe HValue
    241 }}}
    242 which returns a "just return the wrapped thing" if it is one of the Jump names and Nothing otherwise.
    244 This is necessary because a TH function might contain a call to a breakpoint function So if the module it lives in is compiled to bytecodes, the breakpoints will be desugared to 'jumps'. Whenever this code is spliced, the linker will fail to find the jumpfunctions unless there is a default.
    246 Why didn't I address the problem by forbidding breakpoints inside TH code? I couldn't find an easy solution for this, considering the user is free to put a manual breakpoint wherever.
    248 Why did I introduce the default as a special case in the linker?
    250 I considered other options:
    251  * Running TH splices in an extended link env. This would probably scatter breakpoint related code deep in the typechecker, and is ugly.
    252  * Making the 'jump' functions real, by giving them equations and types, maybe in the GHC.Exts module. This solution seemed fine but I wasn't sure of how this would interact with dynamic linking of 'jumps'.
    255 === A note about bindings in scope in a breakpoint ===
    256 While I was trying to get the generated core for a breakpoint to lint, I made the design decision of not making available the things bound in a recursive group in the breakpoint context. This includes lets, wheres, and mdo notation. The latter case however is not enforced: I haven't found the time to work it out yet.
    259 = Dynamic Breakpoints =
    260 The approach followed here has been the well known 'do the simplest thing that could possibly work'. We instrument the code with 'auto' breakpoints at event ''sites''. Currently event sites are code locations where names are bound, and statements:
    261  * Binding sites (top level, let/where local bindings, case alternatives, lambda abstractions, etc.)
    262  * do statements (any variant of them)
    264 The instrumentation is done at the desugarer too, which has been extended accordingly. We distinguish between 'auto' breakpoints, those introduced by the desugarer, and 'normal' breakpoints user created by using the `breakpoint` function directly.
    267 == Overhead ==
    268 The instrumentation scheme potentially introduces overhead at two stages: compile-time and run-time. Compile-time overhead is unnoticeable for general programs, although there are no benchmarks available to sustain this claim. Run-time overhead is much more noticeable.
    269 Run-time overhead has been measured informally to range in between 9x and 25x, depending on the code of the program under consideration.  '''This is no longer true. ''' After extensive benchmarking and tweaking, overhead is down to 166% in average, 560% worst case, measured over the entire nofib suite.
    272 With an always-on breakpoints scenario in mind, we do a number of things to mitigate this overhead in absence of enabled breakpoints. One of these is to allow a ghc-api client to disable auto breakpoints via the ghc-api functions:
    273 {{{
    274 enableAutoBreakpoints  :: Session -> IO ()
    275 disableAutoBreakpoints :: Session -> IO ()
    276 }}}
    278 GHCi would keep breakpoints disabled until the user defines the first breakpoint, and thus for normal use we could keep the -fdebugging flag enabled always.
    280 The problem is that to make the implementation of `disableAutoBreakpoints` (`enableAutoBreakpoints resp.)  effective at all we need to implement it by relinking the `breakpointJumpAuto` function to a new "do nothing" lambda (to the user-set bkptHandler resp.).
    282 This would imply a relink, which is quite annoying to a user of GHCi since any top level bindings are lost. This is why this functionality is only a proof of concept and is disabled for now. I wish I had a better understanding of how the dynamic linker and the top level environment in ghci work.
    284 We also try to do some simple breakpoint coalescing.
    286 === Breakpoint coalescing ===
    287 ''.. implemented, to be documented..''
    289 == Modifications in the renamer ==
    290 This section is easy. There are NO modifications in the renamer, other than removing Lemmih's original code for the `breakpoint` function. All the stuff that we had originally placed here was moved to the desugarer in the final stage of the project.
    292 == Modifications to the desugarer ==
    293 Extended to carry the local scope around. Also extended to desugar breakpoint* to breakpoint*Jump, and to produce the dyn breakpoints instrumentation under -fdebugging.
    295 == Passing the sitelist of a module around ==
    296 After  a module has been instrumented with dynamic breakpoints, the list of sites where breakpoints have been injected must be surfaced to the ghc-api. ModGuts has a new field mg_dbg_sites, and from there it is stored in ModDetails.md_dbg_sites
    298 == The `Opt_Debugging` flag ==
    299 This is activated in command-line via `-fdebugging` and can be disabled with `-fno-debugging`.
    300 This flag simply enables breakpoint instrumentation in the desugarer.
    302 `-fno-debugging` is different from `-fignore-breakpoints` in that user inserted breakpoints will still work.
    304 == Interrupting at exceptions ==
    305 Ideally, a breakpoint that would witness an exception would stop the execution, no more questions. Sadly, it seems impossible to 'witness' an exception. Throw and catch are essentially primitives (throw#, throwio# and catch#), we could install an exception handler at every breakpoint site but that:
    306  * Would add more overhead
    307  * Would require serious instrumentation to embed everything in IO, and thus
    308  * Would alter the evaluation order
    310 So it is not doable via this route.
    312 We could try and use some tricks. For instance, in every 'throw' we spot, we insert a breakpoint based on the condition on this throw. In every 'assert' we do the same. But this would see only user exceptions, missing system exceptions (pattern match failures for instance), asynchronous exceptions and others. Which is not acceptable imho.
    314 I don't know if a satisfactory solution is possible with the current scheme for breakpoints.
    316 == The breakpoints api at ghc-api ==
    317 Once an 'auto' breakpoint, that is a breakpoint inserted by the renamer, is hit, an action is taken. There are hooks to customize this behaviour in the ghc-api. The GHC module provides:
    318 {{{
    320 setBreakpointHandler :: Session -> BkptHandler Module -> IO ()
    322 data BkptHandler a = BkptHandler {
    323      -- | What to do once an enabled breakpoint is found
    324      handleBreakpoint  :: forall b. Session
    325                                   -> [(Id,HValue)]        -- * Local bindings and their id's
    326                                   -> BkptLocation a    -- * Module and Site #
    327                                   ->  String                 -- * A SrcLoc string msg
    328                                   -> b                         -- * The arg. to the breakpoint fun
    329                                   -> IO b
    330      -- | Implementors should return True if the breakpoint is enabled
    331    , isAutoBkptEnabled :: Session
    332                                 -> BkptLocation a      -- * Module and Site #
    333                                 -> IO Bool
    334    }
    335 }}}
    337 The Ghci debugger is a client of this API as described below.
    339 == The D in Dynamic Breakpoints ==
    341 In order to implement the 'isAutoBkptEnabled' record, when a breakpoint is hit GHCi must find out whether that site is enabled or not. GHCi thus stores a boolean matrix of enabled breakpoint sites. This scheme is realized in [ [[GhcFile(compiler/main/Breakpoints.hs)]]]:
    342 {{{
    343 data BkptTable a  = BkptTable {
    344      breakpoints :: Map.Map a (UArray Int Bool)  -- *An array of breaks, indexed by site number
    345    , sites       :: Map.Map a [[(SiteNumber, Int)]] -- *A list of lines, each line can have zero or more sites, which are annotated with a column number
    346    }
    347 }}}
    349 Since this structure needs to be accessed every time a breakpoint is hit and is modified extremely few times in comparison, the goal is to have as fast access time as possible. All of the overhead in our debugger is going to be caused by this operation.
    351 Alternative designs should be explored. (Using bits instead of Bools in the matrix? discard the matrix thing and use an IORef in every breakpoint? some clever trick using the FFI?). Suggestions are welcome.
     185(If for some reason you want to check the original solution, browse the history for this wiki page.)
    353187= Pending work =
    355 Call stack traces.
    357 Interruption at unexpected conditions (expections).
    359 Rewrite of the Term pretty printer at  [[GhcFile(compiler/ghci/RtClosureInspect.hs)]]
     189Tests, tests, tests. Specially exotic features including rank-2 types and GADTs.
    361191= General Comments =
    366196An extensive suite of tests should be needed to easily detect when it lags back changes in GHC. Fortunately the code itself isn't too long nor spread.
    368 The '''breakpoint instrumentation''' on the contrary is spread everywhere the desugarer, but is less likely to break and in less spectacular ways if it does. For instance, one might lose access to implicit parameters in a breakpoint, or things like that. Tricky stuff are Template Haskell, 'deriving' generated code, breakpoint coalescing..
    370 The '''breakpoint desugaring''' depends only on the Core representation, which I think is stabilizing soon with System Fc. This is the less likely piece to break in my opinion, and the easiest to restore.
    372 The '''debugger''' itself, i.e. the user interface offered by InteractiveUI, should virtually maintain itself once it is bug-free (which I don't claim it is), as long as future changes to ghci itself respect the few things it assumes.
    374 === Breakpoints and threads ===
    376 In a multi-threaded program breakpoints and threads must be handled carefully. Consider the case that one running thread hits a breakpoint and then another running thread also hits a breakpoint. What should happen?
    378 One important note is that when a breakpoint is hit control returns to a GHCi prompt, which has a command line on a terminal. Obviously this prompt is not designed to be run concurrently. So, in the very least, there should only be on thread allowed to enter the debugging prompt at any one time. One mechansim to support this would be to lock entry into the debugger prompt with an MVar. Any other thread which hits a breakpoint will then have to wait on the MVar before proceeding to the prompt. Another more substantial option is to have the schedular stop all running threads whenever a breakpoint is entered. This would allow more features in the debugger, such as the ability to inspect the stacks of running threads and so forth. It also seems to be consistent with the way that gdb works and the java debugger, see [].