Hacker News Reader

Comment by Waterluvian | Hacker News Reader

Newbie question:

How hard would it be for a text editor to highlight all lines that do or might allocate? Can they be known statically?

rust-analyzer could probably do it. That information isn't exposed in type signatures, though, so it'd have to have full access to the source of everything and a good understanding of the standard library (and would fail if you added your own “might allocate” by going around the back of the global allocator).

You could definitely show all the lines that might allocate statically.

I'm pretty sure catching this in all cases would involve solving the Halting Problem.

I think if we wanted a concrete answer you’d be right.

But I feel like a static analyzer could clearly identify “this line can allocate” just by knowing what language features can allocate. And for third party library methods “does this function have anything inside of it that could allocate?”

If you're allowed to have false positives, it's not so hard. Like "this function allocates if A or B is true" just becomes "this function can allocate". It's not so different from finding functions that can panic.

I’m fairly certain that this does not require solving the halting problem. Fundamentally, every line of code can be transformed to the underlying code constructs, and those could be checked for allocations. Doing this in an efficient manner is probably hard, but certainly not impossible

    fn maybe_alloc() -> Vec<usize> {
        if collatz_conjecture_is_true() {
            vec![42]
        } else {
            vec![]
        }
    }

    fn main() {
        let v = maybe_alloc(); // Does this allocate?
    }

You would just assume it does. Really you want to detect all places that might allocate.

You are right. It’s definitely possible if you accept false positives.

You can absolutely statically determine where allocations happen.

You can't know for sure if all of those places are reachable in a running program, but that's not necessary to solve this problem.

Reply on news.ycombinator.com