Recursion lint

[Pyriphlegethon]

Although recursion isn't bad in and of itself, it can often lead to infinite loops. Also some companies don't allow their programmers to use recursion (See this well known paper by NASA).
Jonathan Blow implemented a similar lint for his new programming language in this video.
This lint should probably be allow by default, because in most cases recursion is fine to use.

[rgiot]

I guess this issue has not been solved because it is quite complex to do.
There is however a simple pattern that may be detected without too much difficulties (I personnaly do quite often this mistake):

struct MyStruct {
 a_field: Vec<Something>
}

impl MyStruct {
 pub fn a_field(&self) -> &[Something] {
   &self.a_field()
 }
}

instead of

struct MyStruct {
 a_field: Vec<Something>
}

impl MyStruct {
 pub fn a_field(&self) -> &[Something] {
   &self.a_field
 }
}

[oli-obk]

direct recursion should already be caught by rustc: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=0c6c409030e91d68f66607292b736332

warning: function cannot return without recursing
 --> src/lib.rs:8:5
  |
8 |     pub fn a_field(&self) -> &[Something] {
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot return without recursing
9 |         &self.a_field()
  |          -------------- recursive call site
  |
  = note: #[warn(unconditional_recursion)] on by default
  = help: a `loop` may express intention better if this is on purpose

[felix91gr]

So if I understand this correctly, this issue is actually not talking about detecting infinite recursion. It's asking for a clippy::restriction lint against recursion. Something the user can turn on to disable recursion entirely. @Pyriphlegethon is my assessment accurate?

---

Regarding such a lint:

• The base case should be fairly straightforward (haha famous last words) to catch -- whenever a function calls upon itself.

• More general cases would require to derive the Directed Graph of possible recursive calls, and lint in case it's not Acyclic.

Both cases might give false positives, but I'm not sure how bad this is given that:

1. It's a restriction lint, and
2. The people who want it really want it.

We might eventually be able to reduce the amount of false positives using Value Range Analysis, but that's machinery that the compiler is still years away from having so I think it's fine to "just" do a crude check for recursion and have something useful (if imperfect) for now.

[samueltardieu]

This kind of lint is likely to be implemented as part of the Safety Critial Rust consortium guidelines.

[felix91gr]

This kind of lint is likely to be implemented as part of the Safety Critial Rust consortium guidelines.

Nice!

How does that work... work? Are they making a subgroup of lints in Clippy? Are they making their own linter? Or are they integrating such analyses in the compiler itself? :o

[samueltardieu]

This kind of lint is likely to be implemented as part of the Safety Critial Rust consortium guidelines.

Nice!

How does that work... work? Are they making a subgroup of lints in Clippy? Are they making their own linter? Or are they integrating such analyses in the compiler itself? :o

https://hackmd.io/5xO5VtucR_a8d6JUF6WacQ

[felix91gr]

This kind of lint is likely to be implemented as part of the Safety Critial Rust consortium guidelines.

Nice!
How does that work... work? Are they making a subgroup of lints in Clippy? Are they making their own linter? Or are they integrating such analyses in the compiler itself? :o

https://hackmd.io/5xO5VtucR_a8d6JUF6WacQ

Oh hell yeah.

I wonder... 🤔 Do they have a repo, or some place where they open issues / track goals? Because maybe it's worth it to go there and link them to this issue. That way they can take (or not) ownership of the implementation so that we're not duplicating efforts.

(Specially since they're bound to understand their own use case quite well, and I would expect that they'd have more funds to dedicate to lint-making).

[PLeVasseur]

I have been summoned ☁

Thanks for reaching out about this @felix91gr and pointing it out!

This does indeed look like a useful lint 👁 👁

[felix91gr]

@rustbot claim