Implement Vim's tag stack#38127
Conversation
| buffer: target_buffer_handle, | ||
| range, | ||
| LocationLink { | ||
| origin: None, |
There was a problem hiding this comment.
I don't know enough about this code to know if we can get an origin for this jump
There was a problem hiding this comment.
I think we can use the same location for the target and the origin. This is because origin is only used for naming purposes, and the name of the type should be sufficient for this. I made a PR to your repo that reflects this change zenazn#2
| ) else { | ||
| return Navigated::No; | ||
| }; | ||
| ed.read(cx).create_tag_stack_entry(tag, cx); |
There was a problem hiding this comment.
We chatted on Tuesday about what to do in the case where go-to-definition is ambiguous, and Zed opens a multibuffer of all of the options. I decided that a Good Enough™ solution was to treat the multibuffer itself as the jump target. We can improve this if we'd like, but honestly it feels fine to me
|
Great work! I have a crude list of fast follows for commands and keybinds (some of which you have already mentioned) that I think we should do. I would love to knock some of these out after this gets merged.
This mostly came from https://vimdoc.sourceforge.net/htmldoc/tagsrch.html |
cbbb22f to
0b04930
Compare
|
Thanks! I'll try and take more of a look in the next few days (though I am quite behind on code review, so I'm going to be a bit slower than I want to be) |
This commit makes it clear how much the changes here spill out into the rest of the repo. Being able to clone NavHistory allows us to fork history when splitting (implementation in next commit)
This change is hopefully mildly useful for everyone (you can now use splits to "explore" history without risking giving up on your current state), and will be very helpful in a few moments for implementing the Vim tag stack
Previously, even when "always" was set, a nav history entry was not added if (e.g.,) the definition was on the same line as the place we were jumping from. But always means always! In particular, this makes it much easier to interact with navigation history from code, because its behavior is more predictable. Also, abstract out `navigation_data`, because we'll need it in just a sec.
Nothing is adding entries to the tag stack yet, but were they to exist this is how we'd navigate between entries: - A good mental model: the tag stack is "super-back" and "super-forward" in navigation history - Every time we go-to-definition, that navigation (i.e., the edge between those two history states) gets pushed onto the stack [not yet implemented; see next commit] - When we go back to an older tag, we navigate back in history (as if we'd hit "back" a lot) to the moment *before* we navigated to the most recent definition - When we go forward to a newer tag, we navigate forward in history to the moment *after* we navigated to the next definition - In the case that the tag stack refers to history states that are no longer part of navigation history (e.g., they have aged off the back of the stack, or have been truncated off a forward stack because the user has started exploring a different branch of history), we navigate to the expected positions anyways, pretending as if they were still present in navigation history After much thought, I think this is the best way to work Vim's tag stack into Zed's concept model. I think it's especially nice that: - There's nothing Vim-specific about anything in the implementation, even though it's inspired by (and has more-or-less the same semantics as) Vim - There are virtually no changes for users that don't want to interact with the tag stack (two minor changes: the exact history entries that get created are different, and navigation history forks on pane split) - It's possible (and nice, even!) to bounce back and forth between back/forward and older/newer tags. They bring different things to the table, and work very well together. The hardest part of the implementation is stably addressing moments in navigation history: - The current view state is part of navigation history (especially if e.g., you've hit "back" several times and there are navigation elements both before and after the current moment in history), but is not reified anywhere - There are no stable identifiers anywhere. Even `(pane, location)` can wobble around a little, because a small move to the cursor won't create a navigation history entry, but *will* impact what position is put (back) onto navigation history once we scroll past it The solution I came up with is to number navigation history items starting from 0, and rely on the fact that the common way to manipulate navigation history is adding and removing elements at the end. This has one major caveat, which is that there *is* a circumstance in which we manipulate "middle" entries in history: when we e.g., delete a file. In this case, instead of removing those entries from history, we leave a tombstone. This eliminates the need for re-numbering, which makes the implementation easier.
Whenever we're navigating to a hover link (which is how features like go-to-definition are implemented), add that to the tag stack. This is the equivalent of jumping to a tag in Vim. We could hook in one layer "up," in `go_to_definition_of_kind`, but I chose to hook into hover links because: - Command-click is basically the same as go-to-definition, and it's nice that the two are treated identically. Tag stack users can bounce seamlessly between navigating with their mouse and keyboard. - On a practical level, all the information I wanted was in hover links, and would have been a pain to pipe around to where I needed it This commit additionally calculates and stores a "tag," which is the identifier we jumped to the definition of. This tag isn't used yet, but is helpful when debugging, and would form the basis of a future UI displaying the tag stack.
0bd286b to
35bdfcb
Compare
|
I'm still eager to push this change forward, so let me know if there's anything I can do to help! One thing that might be helpful is for an admin to kick off the tests again—I fixed one clippy error from last time, and I'd be happy fixing any additional failures (I'll be honest—I'm not sure how to run the tests myself locally! I looked in the contributing guide but wasn't able to learn how there) |
|
@zenazn You can run a specific test with
You can find that in the CI here. There is also a section that is not linked from the CONTRIBUTING.md file that gives some contributing advice like how to run tests https://github.com/zed-industries/zed/blob/main/docs/src/development/linux.md#building-from-source |
|
Thanks @AidanV! Save some DB tests (likely because I'm not running some database locally), the tests pass on my laptop. |
|
This is still on my radar (and I am still behind), sorry! |
|
@zenazn Sorry for the slow response. Overall I think we're heading in the right direction, but I am finding the code in the nav history a bit hard to navigate. I think the problem is quite complicated, but the code is probably more complicated than the problem. For example we sometimes mark entries in the stack as deleted, and sometimes remove them from the list. Is there a way to make this always use one approach (probably just removal). Is it the case that tag jumps are a subset of navigation entries? If so then updating the entry to store state about the tag-ness makes more sense to me than having a separate stack (that has both two entries and also two indices?). But I vaguely remember talking about this, and I don't remember what we decided. Another possible idea would be to make the stack consist of enums (so entries can either be navigation entries or tag stack entries); but not sure if that helps tidy up the logic as much. |
|
Thanks for having a look! The code is definitely more complicated than I wanted, but barring a more significant refactor of how navigation history works, I wasn't able to think of a better way. Suggestions very welcome, of course! It's been a while since I wrote the code, but by my memory we ~always have to mark entries as deleted, rather than removing them. This is because navigation entries don't have a stable identity beyond their "depth" in the stack. One experiment you can run yourself is that you can cause navigation history items to "walk around": hit the back button, move the cursor down one row, then the forward button. If you repeat this a bunch, you can cause a navigation history element to move arbitrarily far from where it used to be. So you can't even use Why do we need to identify entries in navigation history at all? It's because the current view of the editor—even if you've scrolled back in history—is not a member of navigation history. Instead, that implicit entry is re-created when you hit either the forward or back button. That makes it difficult to stash extra information on navigation history entries, because any state that cannot be inferred from the current view of the editor cannot be re-created if you were to e.g., churn the entire navigation history stack by hitting back and forward a lot. Because we can't stash information on the main navigation stacks, we need our own data structure that's capable of pointing to positions in navigation history. A diagram, in case that's helpful: (the fact that So, for your question about it being a subset: it mostly is, except for two situations:
An example user story of the second situation:
This second situation isn't something that happens often in my use of the tag stack feature, and so speaking for myself I'd be happy with solutions that didn't consider it! But I can't speak for other vim users, and even still the first ("current view") problem remains. Even given just the first problem, I wasn't able to find a solution that didn't keep its own data structure I noticed that there are some more merge conflicts. Once we get past alignment on the approach I'd be happy to rebase again! |
|
@ConradIrwin to follow up on this, what's a good next step? I could:
I know you're busy and that you want to make sure you understand the code that you'll have to maintain going forward, but from my perspective I'd like to reach some finality to my efforts here |
|
Hi @zenazn my goal is to set aside an hour or two to sit with this and play with it. Necessary complexity is of course necessary, but my "spiny sense" is off with this code as it stands. Sorry for the slow back and forth here, and I want to make sure I can respond with something more useful. I'm happy to pair more if you are, but I think the next step is getting my understanding up to speed. |
|
Thanks again for your patience. I finally got time to sit down with this, and the result is b69a2ea. I realized that in vim, the tag stack and the jump list are completely independent (i.e. going back in the tag stack pushes to the jump list), and so trying to merge the two stacks was a mistake (sorry about that, I think it was my idea). There's still work to do (either on this branch or yours), but I think the direction on the tag-stack-2 branch is less intertwined and a bit easier to follow (though I don't really love the If you want to take it over, that would be great; otherwise I'll continue pushing on this when I get more time. Todo:
|
|
Huh! That doesn’t match my intuition (or, it seems, yours), but it certainly simplifies things to separate them. I don’t use vim’s jumplist and only lightly use zed’s navigation history (which I believe is slightly different?), so I’m indifferent between the approaches. I’m happy to have another stab at this, though if you happen to get to it first, by all means go ahead! |
|
Closing this for now, sorry I didn't get to finishing up my implementation. If someone wants to pick that up, it would be fabulous. |
Happy New Years! This PR is a second take at #38127 (cc @ConradIrwin) This PR is significantly less complicated than the last attempt: while we still keep our data on the `NavigationHistory` object, we no longer tightly integrate it with the existing back/forward "browser history." Instead, we keep our own stack of `(origin, target)` pairs (in a struct to make it easy to extend with e.g., tag names in the future). The PR is split into two separable commits. Most of the implementation is in the second commit, which: - Defines the stack data structure - Implements `pane::GoToOlderTag` and `pane::GoToNewerTag` in terms of the stack - Hooks into `navigate_to_hover_links` to push tag stack entries This last bit is the most fiddly. The core challenge is that we need to keep track of the `origin` location and calculate the `target` location across three codepaths that might involve creating a new editor and/or splitting the pane. One thing in particular I found difficult was that an editor's `nav_history` (an `ItemNavHistory`) seems to be populated asynchronously. Instead of relying on it, I decided in this code to make my own `ItemNavHistory`. I briefly tried to refactor the code in question, but it seemed like it would significantly increase the scope of the change. I prefer this all-in-one tracking centered around `navigate_to_hover_links ` to the `start/finish` approach taken in b69a2ea because I find it easier to convince myself that the right data is being populated at the right times. Of course, let me know if you think there's a better solution. Closes #14206 Release Notes: - ??? I don't know what to write here! Suggestions welcome
Happy New Years! This PR is a second take at zed-industries/zed#38127 (cc @ConradIrwin) This PR is significantly less complicated than the last attempt: while we still keep our data on the `NavigationHistory` object, we no longer tightly integrate it with the existing back/forward "browser history." Instead, we keep our own stack of `(origin, target)` pairs (in a struct to make it easy to extend with e.g., tag names in the future). The PR is split into two separable commits. Most of the implementation is in the second commit, which: - Defines the stack data structure - Implements `pane::GoToOlderTag` and `pane::GoToNewerTag` in terms of the stack - Hooks into `navigate_to_hover_links` to push tag stack entries This last bit is the most fiddly. The core challenge is that we need to keep track of the `origin` location and calculate the `target` location across three codepaths that might involve creating a new editor and/or splitting the pane. One thing in particular I found difficult was that an editor's `nav_history` (an `ItemNavHistory`) seems to be populated asynchronously. Instead of relying on it, I decided in this code to make my own `ItemNavHistory`. I briefly tried to refactor the code in question, but it seemed like it would significantly increase the scope of the change. I prefer this all-in-one tracking centered around `navigate_to_hover_links ` to the `start/finish` approach taken in zed-industries/zed@b69a2ea because I find it easier to convince myself that the right data is being populated at the right times. Of course, let me know if you think there's a better solution. Closes #14206 Release Notes: - ??? I don't know what to write here! Suggestions welcome
cc @ConradIrwin @AidanV (thank you for pairing with me!)
Gosh, this turned out to be harder than I thought! But I'm really happy with how things turned out—it's a much better solution than what I had on Tuesday.
I'd recommend reading this commit-by-commit. I tried to leave nice commit messages to make it easier to follow along.
At a high level:
One thing I haven't looked into: Making
<C-t>in Vim usepane: Go to older taginstead ofpane: Go back.Closes #14206
Release Notes: