Changes between Version 25 and Version 26 of GhciDebugger


Ignore:
Timestamp:
Apr 25, 2007 7:40:12 PM (8 years ago)
Author:
mnislaih
Comment:

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

Legend:

Unmodified
Added
Removed
Modified
  • GhciDebugger

    v25 v26  
    1515
    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:
    1818{{{
    1919obtainTerm :: Session -> Bool -> Id -> IO (Maybe Term)
     
    4646
    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
    5349
    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
    64 
    65 data Closure = Closure { tipe         :: ClosureType
    66                        , infoTable    :: StgInfoTable
    67                        , ptrs         :: Array Int HValue
    68                        , nonPtrs      :: ByteArray#
    69                        }
    70 
    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 }}}
    82 
    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.
    91 
    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.)
    9351
    9452=== Recovering non-pointers ===
     
    11068
    11169
    112 === Type reconstruction ===
     70=== Type Reconstruction ===
    11371Type reconstruction is the process of recovering the full type of a closure which has a polymorphic dataCon.
    11472
     
    12583}}}
    12684
    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.
    12886
     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).
    12988
    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.
    132 
    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 ===
    13490
    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)]].
    13794
    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.
    139 
    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.
    14497
    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.
     100
     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).
     102
     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.
     104
     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:
    147106
    148107{{{
     108map :: (a -> b) -> [a]->[b]
     109map f x = ...
     110}}}
     111
     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.
     114
     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
     120
     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.
     123
     124==== Example ====
     125This is an example of type reconstruction/refinement
     126in an (allegedly extreme) debugging session snippet:
     127
     128{{{
     129TODO: Update this example
     130
    149131Local bindings in scope:
    150132  r :: a
     
    188170Note how the type of the binding `r` gets updated during the debugging session.
    189171
    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
    193172
    194 I just noticed that this won't detect refinements as: `Either a b` goes to `Either a a`
    195173
    196 There is probably an easy to formulate optimum criteria, but I can't figure it out for now :(
    197 
    198 One more thing, newtypes need to be flattened before doing the unification; type reconstruction may not be able to recover the newtype representation.
    199174
    200175=== Pretty printing of terms ===
     
    206181
    207182= Breakpoints =
     183UPDATE: This is now done differently. See NewGhciDebugger
    208184
    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
    219 
    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.
    229 
    230 This transformation is loosely formalized in GhciDebugger/BreakpointJump
    231 
    232 The site number is relevant only for 'auto' breakpoints, explained later. For the other two types of breakpoints its value should be 0.
    233 
    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.
    235 
    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.
    243 
    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.
    245 
    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.
    247 
    248 Why did I introduce the default as a special case in the linker?
    249 
    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'.
    253 
    254                                    
    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.
    257 
    258 
    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)
    263 
    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.
    265 
    266 
    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.
    270 
    271 
    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 }}}
    277 
    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.
    279 
    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.).
    281 
    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.
    283 
    284 We also try to do some simple breakpoint coalescing.
    285 
    286 === Breakpoint coalescing ===
    287 ''.. implemented, to be documented..''
    288 
    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.
    291 
    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.
    294 
    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
    297 
    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.
    301 
    302 `-fno-debugging` is different from `-fignore-breakpoints` in that user inserted breakpoints will still work.
    303 
    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
    309 
    310 So it is not doable via this route.
    311 
    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.
    313 
    314 I don't know if a satisfactory solution is possible with the current scheme for breakpoints.
    315 
    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 {{{
    319 
    320 setBreakpointHandler :: Session -> BkptHandler Module -> IO ()
    321 
    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 }}}
    336 
    337 The Ghci debugger is a client of this API as described below.
    338 
    339 == The D in Dynamic Breakpoints ==
    340 
    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 }}}
    348 
    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.
    350 
    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.)
    352186
    353187= Pending work =
    354188
    355 Call stack traces.
    356 
    357 Interruption at unexpected conditions (expections).
    358 
    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.
    360190
    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.
    367197
    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..
    369 
    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.
    371 
    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.
    373 
    374 === Breakpoints and threads ===
    375 
    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?
    377 
    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 [http://sourceware.org/gdb/current/onlinedocs/gdb_6.html#SEC45].