6 ms·

Flowistry helps you understand Rust programs with program analysis

152 points by ibraheemdev 5y ago

WhatIsDukkha 5y ago
Looks cool, wouldn't it be better as part of rust analyzer?
- wcrichton 5y ago
  Ideally yes. But Flowistry relies on Rust's borrow checker, and Rust Analyzer does not yet support borrow checking.
rrobukef 5y ago
Prediction: Coming soon to every language and IDE.
- ithkuil 5y ago
  This kind of analysis is not quite possible to perform with all languages. With some languages doing this kind of data flow analysis basically requires you to run the code and as soon as you perform IO you're out of luck.
  - wcrichton 5y ago
    This is right -- the analysis here uses aspects of Rust which don't exist in other languages. Specifically, transitive mutability markers (&T vs. &mut T) and lifetime-based alias-analysis.
    - baq 5y ago
      surely you could guess some of that some of the time? no idea, have zero experience in the space, but it doesn't sound completely impossible.
      - ithkuil 5y ago
        sure you can guess; it all depends how much do you care if you cat't really trust that your IDE tells you.
      - pornel 5y ago
        There are many cases where such analysis quickly becomes exponentially expensive (e.g. nested loops or ifs) and/or requires analyzing whole program at once (to know whether anything anywhere might be holding a reference to the value you're checking), and there are patterns of code that are provably impossible to analyze (halting problem). There are static analyzers that try their best getting this data, but with arbitrary references without clearly annotated lifetimes that can very often become a stack of "well, it depends" to the point the analysis has to give up. Deduction of lifetimes in statically-typed languages without a borrow checker is very similar to deduction of types in dynamically-typed programs.
jph 5y ago
Brilliant. This tracing technique is great for Rust and Code, and likely many more languages and editors. I'm glad to be an early adopter. Thank you!
zinclozenge 5y ago
Looks amazing, I wonder how possible it would be to port it to jetbrains ide.
noneeeed 5y ago
Nice. Dataflow analysis is really quite useful, this is making me think I should take a good look at Rust. I used to work in SPARK and I miss the analysis tools we had. The insights that flow analysis could give you in a tight loop was so useful.
nsm 5y ago
One of the authors (Vastraukas) was also an author on “ Using Lightweight Formal Methods to Validate a Key-Value Storage Node in Amazon S3” which seems relevant (Rust code base), but does not mention this tool. I wonder if there is any relation. https://www.amazon.science/publications/using-lightweight-formal-methods-to-validate-a-key-value-storage-node-in-amazon-s3 https://www.amazon.science/publications/using-lightweight-fo...
- wcrichton 5y ago
  I am the main author of the tool. Vytautas has helped me get the Rust compiler integration set up :-) The closer relation would be to Prusti [1] which is Vytautas' project on verifying Rust codebases. We use the same IR emitted by the Rust compiler. [1] https://github.com/viperproject/prusti-dev https://github.com/viperproject/prusti-dev
shock 5y ago
FWIW, Atlas(Eclipse plugin) exists for Java and is very advanced.
- wcrichton 5y ago
  Thanks for the reference! I hadn't heard of Atlas before and it seems super relevant.
jeremysalwen 5y ago
Hmm, the examples given show local analysis, within a single function. Where this sort of analysis really shines is with global analysis where you can trace dataflow across functions, and even across abstract interfaces. I have only seen this previously with Java code in intellij. I assume this is not yet supported by flowistry, otherwise it would be loudly advertised?
- wcrichton 5y ago
  Yes, Flowistry only supports single-function analysis right now. Interprocedural analysis is my next goal. FWIW, part of the technical contribution of Flowistry is being able to analyze influence (or really effects / mutation) locally. With Rust, I can use the type of a function (as opposed to its definition) to soundly approximate what variables it will mutate, and how it affects what references point-to.
necubi 5y ago
This seems incredibly cool. Do you know how hard it would be to port it to intellij?

152 points by ibraheemdev 5y ago

WhatIsDukkha 5y ago

Looks cool, wouldn't it be better as part of rust analyzer?

wcrichton 5y ago
Ideally yes. But Flowistry relies on Rust's borrow checker, and Rust Analyzer does not yet support borrow checking.

rrobukef 5y ago

Prediction: Coming soon to every language and IDE.

ithkuil 5y ago
This kind of analysis is not quite possible to perform with all languages. With some languages doing this kind of data flow analysis basically requires you to run the code and as soon as you perform IO you're out of luck.
- wcrichton 5y ago
  This is right -- the analysis here uses aspects of Rust which don't exist in other languages. Specifically, transitive mutability markers (&T vs. &mut T) and lifetime-based alias-analysis.
  - baq 5y ago
    surely you could guess some of that some of the time? no idea, have zero experience in the space, but it doesn't sound completely impossible.
    - ithkuil 5y ago
      sure you can guess; it all depends how much do you care if you cat't really trust that your IDE tells you.
    - pornel 5y ago
      There are many cases where such analysis quickly becomes exponentially expensive (e.g. nested loops or ifs) and/or requires analyzing whole program at once (to know whether anything anywhere might be holding a reference to the value you're checking), and there are patterns of code that are provably impossible to analyze (halting problem). There are static analyzers that try their best getting this data, but with arbitrary references without clearly annotated lifetimes that can very often become a stack of "well, it depends" to the point the analysis has to give up. Deduction of lifetimes in statically-typed languages without a borrow checker is very similar to deduction of types in dynamically-typed programs.

jph 5y ago

Brilliant. This tracing technique is great for Rust and Code, and likely many more languages and editors. I'm glad to be an early adopter. Thank you!

zinclozenge 5y ago

Looks amazing, I wonder how possible it would be to port it to jetbrains ide.

noneeeed 5y ago

Nice. Dataflow analysis is really quite useful, this is making me think I should take a good look at Rust. I used to work in SPARK and I miss the analysis tools we had. The insights that flow analysis could give you in a tight loop was so useful.

nsm 5y ago

One of the authors (Vastraukas) was also an author on “ Using Lightweight Formal Methods to Validate a Key-Value Storage Node in Amazon S3” which seems relevant (Rust code base), but does not mention this tool. I wonder if there is any relation. https://www.amazon.science/publications/using-lightweight-formal-methods-to-validate-a-key-value-storage-node-in-amazon-s3 https://www.amazon.science/publications/using-lightweight-fo...

wcrichton 5y ago
I am the main author of the tool. Vytautas has helped me get the Rust compiler integration set up :-) The closer relation would be to Prusti [1] which is Vytautas' project on verifying Rust codebases. We use the same IR emitted by the Rust compiler. [1] https://github.com/viperproject/prusti-dev https://github.com/viperproject/prusti-dev

shock 5y ago

FWIW, Atlas(Eclipse plugin) exists for Java and is very advanced.

wcrichton 5y ago
Thanks for the reference! I hadn't heard of Atlas before and it seems super relevant.

jeremysalwen 5y ago

Hmm, the examples given show local analysis, within a single function. Where this sort of analysis really shines is with global analysis where you can trace dataflow across functions, and even across abstract interfaces. I have only seen this previously with Java code in intellij. I assume this is not yet supported by flowistry, otherwise it would be loudly advertised?

wcrichton 5y ago
Yes, Flowistry only supports single-function analysis right now. Interprocedural analysis is my next goal. FWIW, part of the technical contribution of Flowistry is being able to analyze influence (or really effects / mutation) locally. With Rust, I can use the type of a function (as opposed to its definition) to soundly approximate what variables it will mutate, and how it affects what references point-to.

necubi 5y ago

This seems incredibly cool. Do you know how hard it would be to port it to intellij?