Borrow visualizer for the Rust Language Service

[Nashenas88]

Gonna be a little late to work this morning, but oh so worth it:

cargo run -- src/main.rs --crate-name borrow_bounds --crate-type bin -g -C metadata=872fa14f57985af3 --out-dir /Users/paul/programming/playground/rust/borrow_bounds/target/debug --emit=dep-info,link -L dependency=/Users/paul/programming/playground/rust/borrow_bounds/target/debug/deps --extern error_chain=/Users/paul/programming/playground/rust/borrow_bounds/target/debug/deps/liberror_chain-554f08ea2cb4f0f5.rlib --extern regex=/Users/paul/programming/playground/rust/borrow_bounds/target/debug/deps/libregex-a99351f81f55a22d.rlib  --sysroot=$(rustc --print sysroot)
    Finished debug [unoptimized + debuginfo] target(s) in 0.0 secs
     Running `target/debug/borrow_bounds src/main.rs --crate-name borrow_bounds --crate-type bin -g -C metadata=872fa14f57985af3 --out-dir /Users/paul/programming/playground/rust/borrow_bounds/target/debug --emit=dep-info,link -L dependency=/Users/paul/programming/playground/rust/borrow_bounds/target/debug/deps --extern error_chain=/Users/paul/programming/playground/rust/borrow_bounds/target/debug/deps/liberror_chain-554f08ea2cb4f0f5.rlib --extern regex=/Users/paul/programming/playground/rust/borrow_bounds/target/debug/deps/libregex-a99351f81f55a22d.rlib --sysroot=/Users/paul/programming/rust/x86_64-apple-darwin/stage2`
Looking at nodeid 100
lo: 1292, hi: 1295
found matching block: NodeLocal(pat(100: tcx))
Found 16 loans within fn identified by 100:
NodeLocal(pat(100: tcx))
NodeExpr(expr(185: move |compile_state: &mut driver::CompileState| {
let tcx =
... lots more lines ...
ImmBorrow: Some(src/main.rs:56:18: 56:21)-Some(src/main.rs:52:38: 56:22)
ImmBorrow: Some(src/main.rs:57:80: 57:103)-Some(src/main.rs:57:80: 57:109)
ImmBorrow: Some(src/main.rs:57:111: 57:118)-Some(src/main.rs:57:111: 57:127)
ImmBorrow: Some(src/main.rs:57:129: 57:133)-Some(<std macros>:2:1: 2:60)
ImmBorrow: Some(src/main.rs:57:135: 57:142)-Some(<std macros>:2:1: 2:60)
MutBorrow: Some(src/main.rs:60:13: 69:14)-Some(src/main.rs:60:13: 69:14)
ImmBorrow: Some(src/main.rs:61:38: 61:42)-Some(src/main.rs:61:38: 61:49)
ImmBorrow: Some(src/main.rs:66:32: 66:36)-Some(src/main.rs:66:32: 66:48)
ImmBorrow: Some(src/main.rs:66:55: 66:58)-Some(src/main.rs:66:55: 66:58)
ImmBorrow: Some(src/main.rs:66:73: 66:76)-Some(src/main.rs:66:73: 66:76)
ImmBorrow: Some(src/main.rs:67:33: 67:37)-Some(src/main.rs:67:33: 67:50)
ImmBorrow: Some(src/main.rs:67:57: 67:60)-Some(src/main.rs:67:57: 67:60)
ImmBorrow: Some(src/main.rs:67:75: 67:78)-Some(src/main.rs:67:75: 67:78)
ImmBorrow: Some(src/main.rs:68:70: 68:78)-Some(<std macros>:2:1: 2:60)
ImmBorrow: Some(src/main.rs:68:80: 68:88)-Some(<std macros>:2:1: 2:60)
ImmBorrow: Some(src/main.rs:68:90: 68:99)-Some(<std macros>:2:1: 2:60)

I’ve got to be somewhere immediately after work, but once I’m home I’ll try to clean this up and push to github. This should give us something to work with finally for the plugins. I’ll need to filter more, like only showing the borrows for the currently matching nodeid, but it shouldn’t be too hard from now.

[Nashenas88]

One thing I wanted to add before it slipped my mind. I was thinking about this last night and also saw this issue https://github.com/jonathandturner/rustls/issues/57 for RLS. We could add something to explain the behavior of the spans on top of the normal (whatever it ends up being) borrow spans. I would think this is an additional request from the user since it would only be used as a beginner or in complex code and otherwise be too distracting.

[Nashenas88]

Repo for prototype is up: https://github.com/Nashenas88/borrow_visualizer_prototype

[Nashenas88]

The current version is outputting close to what I think we need to start UI prototypes. What I can’t figure out how to doi s turn off compiler warnings and errors. I’d like the output to just be the json structure. Anyone know how to do this?

[Nashenas88]

Good news everybody! I have a prototype working! Though not totally useable yet, but definitely passes the smoke and mirrors test ;). Here's a gif of it:

[Nashenas88]

So I have some updates from great conversations at Rust Belt Rust with @jntrnr and @nikomatsakis and a few others. One big takeaway is that everyone I showed this to couldn’t wait for it to be finished!

One problem with our current approach of writing the prototype and doing research on the current save-analysis is that they’re based on the HIR implementation, which will be replaced in a few months. Any work we continue to do will be thrown away. Initially I didn’t mind this idea, but thinking on it made me realize our time might be better utilized making UX interactive mockups in HTML. This would allow us to play around with the interactive behavior without having to do all the work of hooking it up to the compiler. This will ideally make it easier for us to throw certain features/behaviors away and hopefully allow us to discover new ones.

One item that came up during lunch was how to determine whether or not beginners are really getting stuck with certain concepts. “Are we really focusing on where people struggle the most?” was more or less the question asked. We even joked (with a little seriousness behind it) that we could implement an “I’m confused” button that once clicked would let you highlight the section of code the user couldn’t wrap their mind around. To that end, we should try to share our mockups with people who are in the process of trying to learn the language as well as with more seasoned Rust devs.

I’m thinking of creating some functioning chunks of code as well as broken ones, and asking people if they can explain or understand the code (how it functions/how the borrows are related as well as how it’s broken). We can then show them how to highlight certain regions and see if it improves their ability to understand. We could also give an example of a usage that @nikomatsakis came up with: underline the entry point to an error that is normally explained over multiple lines (currently IDEs highlight multiple, disjoint spans, but they’re out of order with respect to how the compiler error explains the issue). When a user clicks on that entry point, the borrow regions are highlighted, arrows show the flow between the different conditions that brought about the error, and floating spans of explanations hover next to their corresponding arrow.

I’ll try to elaborate more on some of these details when I have more time.

So for now I think this project has two main goals: Make it easier for people to reason about borrows in code that can compile, and improve the error messages produced in code that doesn’t compile.

For the latter case, @nikomatsakis has 4 specific cases of errors in mind, which I’d love for him to share here. (I can’t recall all of the details after all the conversations, I’ll need to remember to take notes about everything next time). Also, if anyone I spoke to at the conference wants to add in something I missed here, please share.

[Nashenas88]

Sorry I’ve been gone from this thread for so long. Work, interviewing for a new position, holidays, and a sibling’s wedding took up almost all of my time.

During this time I’ve attempted to pull in the latest changes from the compiler, which broke the pre alpha version. I’ve still not had time to fix that, but hopefully I’ll start again next week.

I had an idea on how to improve complex flow visualization. Just how overridden functions in other languages can be shown one at a time, we could do the same and optionally only visualize one thread of execution at a time. There might be cases where a user might want some blocks to be fully visualized while others only have a single thread visualized. We might want to have it configurable per block then (will need to research how/if IDEs expose something like this).

I’ve also been reading more of the borrow checker code and think I’ve found a way to visualize the green highlights from our examples. I’ll implement that soon so I can play around with visualization ideas.

[Nashenas88]

So I was able to work around the compiler issues (turns out the build process and output folder changed a while back, and I was pointing rustup to a 3 month old compilation, d'oh!). I was also able to figure out how moves work and how to find the span of the variable assignment! (kind of).

Regarding variable assignments, I can highlight the scope of the variable using the beginning of the span of the assignment node, and then attempt to use the end of the kill span. The downside to this approach is it doesn't take moves into consideration. I could do it manually by looking for the last move and setting the end of the highlight to the end of the move's span, but this is very brittle because it doesn't validate its behavior with what the compiler is actually doing.

It's actually helped me see that this would require integration into the compiler and would not be possible as a standalone tool (I can't remember if that's been brought up previously). I'd need to know about var assignments, moves, loans and drops. I don't think I'd need anything else (barring edge cases I haven't thought about). The previous items, excluding drops, are available in the AnalysisData struct within librustc_borrowck::borrowck. This may not hold for MIR, but I want to try and get in touch with the compiler team about this. I'm going to try talking to @nrc next week (after Monday, since I'll be celebrating my birthday) about how to integrate this with SaveAnalysis.

And last but not least, here's a screenshot of the latest version:

You'll notice that the green span on the left goes on for too long. It should actually end with the move span on line 70.

I also want to try implementing this in VS Code instead of Atom. Atom groups highlights in such a way that it's impossible to implement the outline idea @eddyb came up with on irc. (Just imagine that there's a single outline wrapping the span rather than an outline following the lines.) It actually converts a single highlight request into multiple lists of spans. The single outline idea would be pretty easy given I have the ability to render an svg path. Also, rather than wrapping each line tightly, I'd have the edges expand to the width of the longest line (or maybe the edge of the screen, long lines going past the screen could make the spans hard to see if we leave out the faint background color).

[Nashenas88]

Progress

I had really nice chats with @nrc and @pnkfelix this week. The one with @pnkfelix was especially helpful in that we realized I can make an assumption on when the "live" scope ends (I need to move it to the end of the first move, if there is one). Non-lexical lifetimes won't be implemented in the version of the borrow checker that this proof of concept is based on, and when we move to the MIR implementation, there's already a MIR item we can use to track the "live" scope, EndRegion. This means implementing on the MIR version early will automatically enable support for non-lexical lifetimes right when it's implemented in the compiler because it will use the same EndRegion item!

As far as design, I've hit roadblocks. Implementing the wrapping outline doesn't seem to be possible in VS Code (with the current API). The outline property doesn't behave the same as you'd expect since VS Code optimizes lines and only includes the html for the visible lines, possibly out of order in the html itself. They also don't expose border properties for specific sides (top, left, bottom, right), so I can't implement an alternative idea.

That alternative idea is to have 8/9 different styling rules to customize the shape of the wrapping span (for edges and corners of borders and maybe one for interior if we keep the faded shading). Atom makes this accessible by allowing standard CSS styling, so I'm going to head back there to see if I can't get it to work (sorry for saying impossible previously!).

Another idea I came up with to deal with the many borrows that overlap (in invalid cases or with many valid, immutable borrows) is to add items before and after that number the spans.

I think adding them in every case might be distracting, but we could be smart and only add them when spans cross each other or begin/end at the same location within a file. I'll have to play around with this.

Here are some screen shots of what I implemented in VS Code:

I changed the behavior from the Atom version where the feature is toggled at the file level. While it's toggled on, clicking anywhere in the file will attempt to compute the regions. The idea was to incorporate the locking behavior mentioned previously, but I hadn't gotten around to it yet.

Here's an example of the "live" region being cut short. Here's it (should be) quite obvious that the second move is illegal.

Here you can see how only the opening of the function starts the "live" region and not the function parameter itself. After seeing this I think we may need to add yet another region to clarify what exactly is being analyzed.

[Nashenas88]

I got the Atom version working with @eddyb's idea. Check it out:

There are some areas where the border is either missing or crosses in too much to the left. This seems to be a limitation of Atom itself. I'm requesting the right position, but

1. Atom doesn't allow you to style anything after the end of the line unless it highlights onto the next line (this follows its own highlighting behavior, and I get around this by setting the end of the last highlight within a line to the 0th position on the next line...)
2. Atom groups multiple spaces at the beginning of a line into a "tab" for highlighting, and assigning a position in the middle of the tab will shift the highlight to the left or right.

The downside to the approach I've taken is any editing will completely ruin the highlighting, so I have to see how I could work with that (either disable editing while visualizing or clearing the highlights on edit, I'm definitely open to alternatives too). I'm happy with the overall look, and tomorrow I'll try adding in the numbered identifiers and maybe start working on the locking functionality.

[Nashenas88]

Just a quick update tonight. What have I been doing the last few months? I was interviewing at way too many places. I finally settled on one (!!!). I’ve been periodically working to add the necessary changes to the compiler, rls-data, rust-analysis and rls. I haven’t gotten to the editor yet but I’m getting close. Compile times suck right now to the point I built a tool just to make an audible noise and leave a message as a notification (a ding and a reminder message have proven to be very helpful) . Everything compiles now, but somewhere along the way the data is getting lost. My logs in the compiler show the data and borrows, but the file rls reads just has an empty array… Again, sorry for the silence all this time. I promise I’ll update within a month next time.

[Nashenas88]

So I finally figured out the problem, I accidentally resolved a rebase merge conflict with HashMap::new rather than passing the borrow information (not easy to debug, orz). At this point I’ve started the first pull request! I’m currently waiting for https://github.com/rust-lang/rust/pull/42471 to go through before I can update my changes in the compiler again. In the meantime I’ve been working on expanding rls_vscode to handle the new, custom message. I don’t expect the many necessary pull requests to go quickly. There’s a lot that I’m sure I’m no expert on, and I want to make sure only the right, necessary and performant changes go through. It would be awesome if it could all be in before the next conference, but I’m not making any bets on it. I’ll also be working on adding this to the atom extension for RLS because atom gives us much more flexibility with the design.

Update: If anyone wants to take an early look at the compiler changes and give me any feedback now, take a look here.

[nrc]

I’ve been working a bit with @Nashenas88 on irc. I’m really exicited to see this develop!

[Nashenas88]

To start off, work here is currently going to be delayed. So I had opened a bunch of pull requests for the implementations (the ones for rls-data (#5 and #6) got in and are behind a feature flag). Here are the ones for rls-analysis#71, rls#387 and rust#42733. I had a feeling the changes to the compiler were going to need a serious redesign, and I was right. What I had thought of, and not prepared enough for, was how these changes would affect the future MIR work on the borrow checker. One awesome outcome of this is that Niko asked if I’d like to work on the non-lexical lifetimes (NLL) implementation! For the time being I have to put this to the side because the way NLL works won’t be compatible with my current implementation. The NLL work should go very quickly in comparison to the visualizer (I only need to work in stage1 of the compiler rather than stage3 + external crates), so I’ll do my best to get this back on track quickly once that’s over. I promise!

[Ixrec]

Don’t worry about it. As important as a visualizer would be, non-lexical lifetimes probably are a bigger priority, since NLL should dramatically reduce the number of cases where we’d need to consult a visualizer in the first place. Plus, my number one concern with the visualization ideas suggested so far has always been that they seem to work far better for (or only for) lexical lifetimes rather than non-lexical ones, so if anything you working on NLL directly means the visualizer we’ll eventually get has a far better chance of doing something useful in all of the weird corner cases where we really need its help, rather than having to be thrown out and redesigned as soon as NLL ships.

[Nashenas88]

And we're finally back! Had a chat with @nikomatsakis early this morning over the next steps here, and we wanted to go back to the design phase. NLL has some interesting behavior that we want to account for and situations to make more obvious. The goal is to try to think of the best possible way to visualize "something" (or somethings..., different visualizations for different information from the code) and only then limit ourselves based on what we can pull from the compiler and what IDEs allow us to draw. The idea being that we might even work with IDE maintainers to expand their functionality to support our designs (thinking BIG here). So here are some of the ideas we came up with this morning, plus what I had worked on before:

From Niko (with some slight formatting improvements for easier readability in a forum vs chat):

... I feel like in Rust the key thing you need to know about any variable, typically, is whether it represents owned or borrowed data ... I imagined the borrow visualizer working sort of like: you highlight a particular borrow and it tells you how long it lasts. ...In order to visualize the overall states of the variable, I would have thought we might color every reference to it, and then, (maybe) if you put the cursor over a borrowed reference, it could put an arrow (or highlight) the place where the borrow occurred. But that doesn't let you see in advance of referencing a variable where it is used. ... My main motivator for the "always on syntax highlighting" was to push people to think about "owned/borrowed".

Example of arrow use in Objective-C tooling

Leads us to:

struct Foo<'a> {
    bar: &'a Bar
}

let foo: Foo<'a>

• Always on mode: Differentiate owned vs borrowed values (maybe even showing dead values in bad code)
  • "if you have [the struct Foo above] then I had thought that foo would be "owned" but foo.bar would show "borrowed" (as would foo.bar.baz)"
  • Complicated edge cases: How would you highlight something like foo.bar.baz[foo.bar.bax].bay?
• Highlight mode: Highlight regions when a variable is select to show when it's fully modifiable, readable, locked, moved (i.e., the most recent implementation, which btw, has not been maintained, and would take a huge amount of work to port to be up to date)
  • Expanded with Niko's idea: highlight a borrow, show where the borrow originated with an arrow, and where it ends.
  • Complicated edge cases: If you highlight a borrow, and more borrows are made from that, should you show the borrow mode, or the region mode? Can these modes be combined or should they be separated?

Questions going forward:

• Does anyone have additional information/modes they'd like to show?
• Can any improvements be made to these designs?
• Should we start a new thread or continue within this one?

Side notes for the future: We shouldn't limit this design to visual ideas. Attending RustFest in Kiev, I attended a workshop where one of the speakers (who's name I forget at the moment, but I'm sure @Hoverbear will help me remember) was a blind developer who walked us how he does development. One idea I had for enabling blind developers would be a mode that feeds into a text to speech app that might emit different "hums" depending on the owned/borrowed state or the region highlighting, while the text to speech app is reading the code. Alternatively, a different voice could be used to read each state. There might even be a possibility for overlap, but I don't know at what level the audio streams would become "too noisy".

[WalkerCodeRanger]

I just wanted to chime in with a link to my blog post on Rust Lifetime Visualization Ideas. I created some mockups of a different lifetime visualization that could be implemented in an editor. I also point out further issues that will need to be considered if that approach were to be implemented.

[Nashenas88]

Awesome blog post! Unfortunately I haven’t made any progress for about a year now. I’ve been going through some burnout from having overcommitted my time across work, side projects and personal life. That being said, your post really excites me! I’d like to say I’m going to jump back on this right away, but I’m trying to be cautious about overcommitting again.

Some thoughts about additional areas to explore with your idea: how would this work with async/await and generators? I experimented with async/await in nightly, and it requires a slightly different way of thinking when lifetimes are involved. I had been thinking of abandoning the span based approach for a while now. Your post hit on that as well

What if it was something that was rendered in a new tab/window in the editor? This way we’re not limited to the small space on the side. Related to this, one idea I’ve had is to take the user’s existing code and redraw it with nodes representing key changes in lifetimes (I’ll see if I can scribble something together later tonight). The idea being that branching statements can be rendered horizontally rather than vertically as they are in code, and this allows the lifetimes/loans to be rendered without any breaks.

[Nashenas88]

Please excuse my "drawing" skills below. Rushing this out before I get to sleep in case I get too busy to follow up soon.

Where the flows get really complicated to render is when you have to deal with disjoint lifetimes due to NLL. My previous prototypes basically became impossible to read. (If you feel the sidebar design could work, please provide some designs. I think it looks beautiful and would love to make something simpler). So, taking Niko's advice, I decided to go way outside the box. Given this code from NLL:

I was envisioning something like this:

A control flow diagram of your original code, the life of the values are highlighted with a continuous block rather that disjoint segments. I think it's still pretty straight forward to follow, but let me know what you guys think (the boxes are lines are horrendous, but not sure if that's necessary to distinguish the branching going on (imagine many branch arms in a match block).

[Nashenas88]

Just realized I rushed a little too much. I really only intended to highlight lines 14 -> 15 -> 19. The green should also highlight the right, but the mutable borrow of map on line 14 should show distinct and highlight only on the left branch. Let me know if I should upload another “masterpiece” to clarify.