Two further notes: this patch includes GPR#2284. Also, it adds two new flags (-dlambda-loc and -drawlambda-loc) to print Lambda code with location information attached.

Shouldn't locations be added on all constructors (and then switch to the usual representation with a record containing the location and the "desc")? For instance, why is there no location on Lassign?

I suspect that having locations everywhere, even if not strictly needed for the debugger support, could benefit to e.g. Bucklescript (to produce sourcemaps).

They might not be needed in all cases---I would have to think about each one---but in principle, I agree with what you are saying. The patch is in its current form because I can't really afford to spend any more time on this right now---it has taken a very long time to get even this far---and this version seems to produce pretty good results.

@trefis Thanks for the review; I've pushed changes to fix some of your comments. Could you please resolve the relevant conversations, and then I will attend to the remainder, which I think are more substantial? (I may not be able to come back to this GPR until next week.)

(I also rebased this PR, which involved resolving some conflicts.)

I only looked at the matching.ml code out of curiosity. I think that the code would have been nicer if each piece of code and its location where kept as the same value, instead of being passed around as two independent things. This is what Location.loc is for, and you can reduce the Location. noise by having

type 'a located = 'a Location.loc = { txt: 'a; loc : Location.t }

The synonym type user_code = lambda located might be clarifying in terms of distinguishing code coming from the user program and code generated by the pattern-matching compiler.

We could do that, and generally I would be in favour of such things (except without the extra type alias). However in this case I'm not sure if it's worth it. Bear in mind the proposed change increases allocation.
In the context of the Lambda.t type definition, for the if-then-else case, a record is arguably better anyway; and there aren't actually many other cases where this happens.

I have less of an opinion about using this structure in the matching code itself, but again I suspect the trade-off in increased allocation may not be worth it. @trefis knows far more about this code than I do, and will have a more informed opinion.

As long as this GPR is not felt to be materially decreasing the quality of either Lambda.t (and I think after record-ifying Lifthenelse it does not) or the pattern matching code, it would be better to get this in as-is with a view to adding further improvements afterwards. Such improvements could then be traded off against other potential improvements to the matching code as a whole. There is a large amount of work blocked on this GPR which we really cannot afford to delay any further, and for which human time is already rather scarce.

To reply to @gasche suggestion of using Location.loc (which I believe he made twice), I think Matching is not the right place for it. What you're suggesting is basically what Alain said: "why not have a location on every lambda node?", except Alain was looking at the big picture and you were only looking at the ugly painting.

I also think the whole thing would look nicer if that change was made, however Mark doesn't seem like he wants to do that work; which I guess is lucky for me, because I'm not sure I'd have the patience to review even more such tedious changes.

I'm feeling sorry for having jumped into this discussion, because now I'm in the position of the person that says things nobody wants to hear...

I totally get the idea of saying "I improved this thing a bit, I don't have time for the further improvements you suggest right now so let's stay at that". It's pragmatic and efficient. But I don't think that the part of this PR that I looked at would qualify for that classification. It is rather a case of making things worse in the process of some Important Feature, when we have the impression that a better way exists. Sure, we can leave the cleanup to some other PR but, just as no one wants to do it now, no one will want to do it later and, if we merge now, we will just stay with a codebase that is noticeably harder to evolve and maintain.

If this was a smaller patch, on the road for a less important Important Feature, I'm super-confident that I would be the annoying person to ask for a cleaner rewrite. It is not actually that much work, and keeping the compiler codebase nice and maintainable is arguably Even More Important than most Important Features we add these days. (And I think we should try harder to make things nice from the start when we touch the compiler codebase, instead of aiming for whatever works.)

Some ideas:

• If someone was willing to try a nicer way than passing locations separately everywhere (what I don't like is the fact that the location is decoupled from the thing it is locating, except in the naming of variables), I would be happy to review that part.
• Maybe there is a way to try a better approach on only some fraction of the changes, and post a partial patch (doesn't need to compile) to see how that looks like. This way, we could evaluate alternatives (eg. "having lambda located in bytecomp/matching" vs. "having locations at all Lambda nodes") without having to do full iterations. (We should have done things this way from the start.)

A minor point:

I have less of an opinion about using this structure in the matching code itself, but again I suspect the trade-off in increased allocation may not be worth it.

I don't think we care at all about the cost of allocating one extra block per Lambda node, or (in the case of my more restricted proposal) one extra block per pattern clause and right-hand-side.

I thought some more about the placement of Location.t values within Lambda.t (cf. a comment from @trefis, #2294 (review)). For the moment, I'm only concerned with what is required for the debugging work, rather than anything more general. I think, save for turning Lifthenelse into a record, the current situation should be fine when augmented with a comment (unless I have made a mistake and the following criteria are not satisfied). The comment can explain the following criteria for the positioning of locations:

• There needs to be one at the start of every basic block.

• There needs to be one on any construct that expands to an "operation" (for example, the address of a symbol being moved into a register, or a primitive).

• The Location.t values in the rightmost arguments of the constructors always correspond to the start of the construct itself, which is consistent with the existing ones in such positions.

Adding a record indirection for all nodes therefore seems overkill at the moment. I think that is also likely to be significantly to the detriment of readability, although depending on the rationale, that might be an acceptable trade-off in the future.

I must emphasise that this patch has already received a substantial amount of work (about two solid weeks)---it was far from trivial to thread the necessary location information through the pattern matching compiler. I found it extremely difficult to understand some of that, admittedly very clever, code due to extensive use of partial application and lack of explicit types. If we're worried about the maintainability of this area of code, then I'm afraid the place to turn attention to is the existing code, rather than being over-concerned about the relatively minor additions in this patch. I do not believe those additions will materially affect maintainability, at least once the Lambda.t type has been clarified.

For the record, I don't know if using a record wrapper in Lambda.t is the best approach to make code readable. What is immediately clear in the present patch is that you are passing term fragments and locations (or debug information) for these fragments separately, while it would be nicer if they were passed together as a single object, as it would make clear/obvious what locates what.

One aspect of this discussion I don't really like is the use of the argument "I already spent two weeks on this". You have ambitious goals regarding gdb which require a ton of work, and this is laudable. Writing good code is more work than writing meh code, which means that you have a ton more work, and we should budget for that from the start! Having a ton of work to do does not give anyone license to write bad code, and having discussions on how good the code is, and possibly asking for changes (to, yes, a lot of code), should be on the table for any pull request.

Let's place a moratorium on any further comments until this is revised.

By popular demand, I've pushed a new version of this, which should be much more satisfactory. There were so many additional changes that I've just squashed everything down to a single commit; the best starting point for review is the base revision.

I sat down with @lpw25 and we examined the Lambda.lambda type in detail. We have settled upon a particular rationale as to the placement of locations, which is documented in lambda.mli. I have also reflected this in the Cmm.expression type. There is now a particular notion of "block" which is used not only in the Lambda.lambda type (and analogously in Cmm.expression) but also as the type of "actions" during pattern matching compilation.

Whilst making these changes I'm afraid I felt bound to improve some of the formatting of various functions in matching.ml at the same time, together with improving some naming (and labelling various parameters), so as to make it easier for myself and others to understand what is going on. The diff doesn't look too bad with patdiff but the occasional function may be easier to review in its final state (rather than reading the diff). There will be some more review load imposed by this, but I am sure that it is worth it, with thanks in advance for reviewers' perseverance.

I believe I have addressed all of @trefis 's other comments, as above.

It may be preferable for these locations in some cases to be distinct -- for example if one arm of an Lifthenelse was a function application surrounded by begin and end, then it would be reasonable for the location on the block (in the Lifthenelse arm) to be that of the begin but the location on the application (inside the block) to be on the f x or whatever it is.

I see, but this is not what happens in this PR, right? Anyway, we won't be able to do something more fine-grained than what the Typedtree keeps, which is currently one location for each node.

The natural approach, in my opinion, would be to keep the same scheme as for Parsetree or Typedtree, i.e. attach the location information at each node, in a uniform way. If only for the sake of design uniformity across the compile code base. The introduction of "blocks" goes a long way towards this approach, so I don't understand whether you prefer not to do that because (1) this would be more (invasive) work and you really want to move on -- which I can fully understand, or (2) there are intrinsic benefits of not doing it like that (in which case, I wonder if the same arguments would apply to Parsetree and/or Typedtree).

@alainfrisch I'm not actually sure I know the answer to the first question in all cases -- but I don't think it really matters. The location information is in any case very likely to require tweaking, quite possibly in ways we have not yet foreseen, once we get this whole package of work released.

I explained in the previous comment that I see no technical merit for having anything beyond the existing "blocks" approach at this stage. I don't think we should be cluttering up intermediate languages with unnecessary information, both because it can materially impact upon code clarity at sites where terms are constructed and deconstructed, and because it is wasteful at runtime.

I do also really want to move on, so we can get the benefits of this work to users. To this end, I would very much appreciate feedback on the actual logic within this patch, in particular the pattern matching compilation parts. The idea is that the locations put on terms by the match compiler should reflect the progress of a pattern matching at a fine level to the fullest extent possible.

(2) there are intrinsic benefits of not doing it like that

In the middle-end languages (lambda, clambda, flambda, cmm) it doesn't make sense to talk about the locations of many of the constructs. Things like lets and variable uses are artefacts of the IRs themselves not constructs in the original source, and not things that produce instructions in the output. The things that locations do make sense for are essentially the operations (e.g. primitives and function applications) which should always correspond to a corresponding expression in the source and which directly produce assembly instructions, along with parts of the control structure (e.g. the branches) which also appear in the source and can be "blamed" for instructions in the output. The current design of this PR attempts to put locations on all of those places.

Can people involved in this PR arrange to make progress? It is blocking related work, but also unrelated one such as #2165. So please don't let this PR stall.

I don't think this PR should be considered blocking for the unrelated #2165. It would be blocking if the other PR depended on a change in this PR (this is not the case), and it would be "nice to wait" to avoid a rebase if the present PR was to be merged imminently (I don't think this is the case either). Let's set #2165 free to live its own exciting PR life.

As to the status of the current PR: personally I think that having more location information in Lambda code is a desirable feature for a variety of use-cases (not in the sense that I can personally name any one use-case that I deeply care about right now, but in the sense that I am convinced reasonable use-cases exist), and I would be willing to finish the review work for this PR (getting Thomas to review my own changes to switch.ml; I also have one-fourth to one-third of the code still to review, which is also likely to require cleanup changes after review) and to get it merged.

On the other hand, clearly @xavierleroy is not happy with the idea of adding more location information in Lambda code, independently of how invasive/ugly the change is (the first version was fairly ugly but I think it can be made a very reasonable, readability-preserving change). I think that it could be possible for me to sneak the commit inside the Treasure Cave without awakening the dragon -- or maybe to persuade the dragon to look elsewhere -- but I have not tried yet. I don't think waiting a few extra weeks would do us any harm.

@gasche Let's please have some discussion between the various people involved in changes (or potential changes) to Cmmgen before proceeding -- we could do this on email. The continual effort to rebase these patches on all sides is significant, and we should try to co-ordinate.

The dragon metaphor is no quite right. The duty of the dragon is to make sure that nothing is taken off the treasure cave. My duty is to make sure that only treasure, and not litter, is stored in the treasure cave. You don't change a part of the compiler as sensitive as the pattern-matching compiler just on a hunch that more location information must be good and may be useful in an indefinite future.

Independently of arguments about dragons, one thing to note is that we could do large-scale testing on pull requests such as this to demonstrate that the generated code does not change.

just on a hunch that more location information must be good

My understanding is that this PR does fix bugs in the locations that OCaml currently outputs for things (maybe in combination with another patch to propagate the data from cmm to the asm I'm not sure). Fixing these bugs seems worth at least the relevant parts of this code -- which I think is basically the non-Switch parts.

getting Thomas to review my own changes to switch.ml; I also have one-fourth to one-third of the code still to review, which is also likely to require cleanup changes after review

I intend to keep my word on that part, however considering the recent discussions about this PR, I think that the changes to Switch should at least be split out of this feature (if they are to be included at all).
Indeed, from what I understood:

• that part of the changes is the most controversial
• we do not have any example where they would be useful
• there are a few different choices (3 IIRC) we could make/should explore w.r.t. what the locations should be

If that part was to be taken out¹, would Heimdallr agree to it being merged?

1: And perhaps some examples were given of situations were this patch does indeed improve the reported locations?

I've removed the Switch parts; we can come back to those later. I've also rebased this onto current trunk.

Almost all the changes to Cmm have also been removed from this patch. I'm going to present some of these as a separate PR as I think they have a fair amount of value in themselves (in summary, using the same "block" notion as this patch uses for Lambda simplifies the Cmm language types).

I would like to argue again that fine-grained location information is of real value for applications other than single-stepping in debuggers. (In fact, the position of single-step points should be marked independently from the location information, but only now are debugging information formats evolving to the point of being able to support that.) This morning, I heard another potential application, which was recovery of accurate source locations as to where particular optimisations had applied. This was in the context of assessing the applicability of existing, mainly Cmm-based, optimisations and deciding whether some new optimisation was worthwhile.

This patch also helps to fix existing problems with the compiler's line number information output (along with a small subsequent patch to Selectgen). Here is a way of visualising an example reported by a developer at Jane Street:

• Go to godbolt.org
• Select language OCaml from the dropdown menu
• Paste the following code into the left-hand pane:

let [@inline never] helper m x = Some (m + x)

let f m x =
  match helper m x with
  | None -> x
  | Some x -> 1 + x
;;

• On the right-hand side the coloured blocks in the assembly code correspond to the coloured lines in the source pane. It can be seen that the location information emitted for both branches of this match are the same!

One use-case I have in mind for location/debug information in pattern-matching (including the Switch part) is profiling tools that let users study mispredicted branches in the binary, and use DWARF information to let users go back to the source code for each branch.

I have seen real-world cases of users wondering about misprediction in pattern-matching-generated code (namely, a case where using a polymorphic variant was faster than a normal variant due to branch predictors fitting the dynamic distribution of input data in the tree-of-tests generated for the (non-consecutive) polymorphic variant tags, beating the jump-table implementation used for (consecutive) variant tags).

@mshinwell why this was closed? There is some work the replaces this? I was rebasing this patch to 4.10