Hacker News Reader

Comment by aarchi | Hacker News Reader

I’m in the early stages of working a compiler in Rust and haven’t gotten to the IR infrastructure yet. With Rust’s borrow checker, how can I make the IR graph safe, with its control flow preds and succs and data flow inputs that make it so there isn’t a clear owner for any node. How does rustc do this?

View on HN

You may find this paper interesting:

GhostCell: Separating Permissions from Data in Rust <https://plv.mpi-sws.org/rustbelt/ghostcell/paper.pdf>

The essential idea is that you can use one of these "GhostCell" structures to assign a lifetime to a related collection of objects (such as the nodes in a graph), which allows the entire graph to be treated as if it had a single owner and a single lifetime rather than a separate owner and lifetime per node.

The paper is relatively recent (2021), and GhostCell is not, so far as I am aware, used in rustc at this point.

Author of the posted repo here! As another commenter posted, I used typed arenas quite a bit, it's not the most ergonomic way to do stuff, but it's quite performant and gets around the lifetime issues.

It looks like this project is using typed arenas a fair bit - https://github.com/SomewhatML/sml-compiler/blob/master/crate...

I don't know the details of how this is being used in the project, but it might be worth investigating.

I struggled with this as well, and ended up making the lexer itself have a lifetime which is that of the full String read from a file, so that every token (and AST node) has the lifetime of the parsed file. I keep their indexes as well so that I can show error messages like rustc itself does (with code snippets and all) which would be hard to do if I didn't have the full source code text available.

Hope that helps.

This sounds a bit like cheating. What if you want to parse a really big file and delete the tokens as soon as you don't need them?

If Rust claims to solve memory management, then we should not fool ourselves by allocating everything in a huge chunk which is then freed when the program ends.

If this is cheating, many real compilers “cheat.” Heck, some of them famously don’t even free it when the program ends, leaving that up to the operating system!

The solution doesn't scale. The moment you need to deal with very large inputs, you will have to rewrite your entire application from scratch.

I prolonged my own path many times in my life, by making things harder than they need to be. (edit) Aspirations acting as a anti-shortcut somehow.

That's why this was not my first choice... but it was just far too hard to implement it otherwise... and then again, once you really think about it, you must keep ALL tokens/AST nodes in memory to be able to analyse and type-check/lint any decent language... so keeping a big Sring in memory while all nodes just point to slices of it is not nearly as wasteful as it might appear at a first glance.

This sound nice and simple. I moving to arenas but is a extra complexity. Can you show how is done? (ie:code!)

https://play.rust-lang.org/?version=stable&mode=debug&editio...

This loses the whitespace and consequently positions... but should be enough to get you started...

I use a UTF-8 crate to split words which keeps all whitespace, so I can keep positions correctly, in case you want to do that:

https://unicode-rs.github.io/unicode-segmentation/unicode_se...

You could look at Cranelift, which I believe uses integer indices, and several datastructures for control-flow vs dataflow.

There is no SSA IR in rustc itself (MIR, regrettably, only lowers control-flow, but uses variables instead of representing dataflow).

> which I believe uses integer indices

So basically it sidesteps the type system issues in a similar way that an inconvenient car trip instead of taking a flight sidesteps the TSA issues? ;)

Adjacency matrices would make ownership clear and solve the single-writer/multiple-reader issue because nodes wouldn't directly reference each other, but it keeps the exact same relationship between nodes, so any memory leaks are still possible (e.g. not cleaning up dead code because it is cyclic and appears to have references). If I'm going to defeat the type system, it seems like raw pointers would be easier.

Reply on news.ycombinator.com