Location stack for MerlinLocate

[mrmr1993]

It would be useful to track all of the locations that resolution passes through when locating an identifier, and allow the user to step backwards and forwards between them. To quote the setup from #1202:

test.ml:

let f x = x

test.mli:

include Intf.S

intf.ml:

module type S = sig
  val f : int -> int
end

In this example, when locating Test.f the locations would be

• test.mli, at the include line
• intf.ml, at the val f declaration
• test.ml, at the let f definition

Similarly, replacing test.ml with

include Test_impl

(where Test_impl defines the value f) would add the definition point of Test_impl.f to the end of this list. If Test_impl also has an interface, the relevant locations from that should be added in-between.

From the user interface side, commands such as :MerlinStepIn/:MerlinStepOut would be useful to navigate this list. A small amount of state would need to be added to track the last located identifier.

As a small extension, a :MerlinStepTo command might be nice to 'start' stepping -- ie. make only the first step -- instead of jumping straight to the definition/declaration as :MerlinLocate currently does.

[rgrinberg]

This would be quite useful for lsp as well. The protocol allows to return a list of definition locations and lets the user browse through them.

[trefis]

That's … not quite how I see things.

Basically, the way I look at it, when you "locate" something the result space can be represented by a binary tree: the root is where you start from, and then at each node you can either: stop, go to the signature where the current node comes from (let's say that's the edge on the left), go to the structure where the current node comes from (let's say that's the edge on the right).

What we currently do when locate is called, is return either the leftmost leaf, or rightmost leaf; depending on whether the user said they preferred signature or structure. (Sometimes we do stop earlier on one of these two branches, for instance when a functor is giving us trouble, but let's just ignore that orthogonal issue).

A fairly straightforward generalization of this would be to return either the left- or rightmost branch, instead of just a leaf. In this case, returning a list of locations makes sense, and there is a clear ordering between them. ( @rgrinberg if lsp and vscode would handle such a list of locations out of the box, we can definitely try and implement that soon! I'll talk with @voodoos about it)

@mrmr1993 does your proposal fit in my "let's describe the answer in terms of a tree" view? Is it some kind of exhaustive traversal of the tree? I think it might be a depth-first traversal, which does make sense. But my intuition is that on complex examples this would be extremely noisy, hard to navigate, and so, not very useful.

[trefis]

Also: it would be very costly. Right now we only explore one branch, and all this is a metaphor, we never actually build the tree. Building it would require loading a lot of cmt and cmti files, which would slow us down considerably, and have a very noticeable impact on our memory consumption.

[trefis]

I do like your proposed UI though!

[mrmr1993]

@trefis you're right, as written my proposal was depth-first. The 'leftmost' and 'rightmost' branches are normally all I would be interested in, and the rest would nearly always be noise. My ideal would be to walk to the leftmost node (the signature item describing the value), and the next step from there 'resumes' the rightmost branch, which it follows to the end (the structure item defining the value).

This leftmost-rightmost traversal may be harder to explain to users though. I could imagine a series of steps like

struct   let _ = A.f end
struct   include M   end (* in A *)
struct   include N   end (* in M *)
sig      include S   end (* signature of N *)
sig      val f : _   end (* in S *)
struct   include T   end (* in N *)
struct   let f = _   end (* in T *)

and it may seem counter-intuitive that it stops stepping through structure items and switches to signature items 'for a while'.

---

I'm not sure if/how it would work with lsp, but on the vim side it would be a nice extension to have :MerlinStepInIntf/:MerlinStepOutIntf and :MerlinStepInImpl/:MerlinStepOutImpl. I can imagine using all of these, each being useful in different situations:

• InIntf at an include M structure item: 'how is the target constrained in this module?'
• OutInf at a let f = _ structure item: 'how and where is this first constrained?', 'does this function argument have an opaque/private type?'
• InImpl at an include M.S signature item: 'I know this signature without stepping through it, where is the implementation coming from?'
  • concrete examples would be Binable.S, Monad.S, etc. for me, where the including interface may still be useful for documentation about the types or behaviour.
• OutImpl at a signature item: 'which module is this signature constraining?'

Since all of the leftward (signature) branches 'hang off' the rightmost branch, these commands have a left/right and up/down feel that makes them fairly easy for me to reason about. I think the expense of these should be more manageable on the vim side too, since we can lazily generate the locations for steps if/when they are taken.