Add direct-recursion Lint

[felix91gr]

Checklist:

• [x] Followed [lint naming conventions][lint_naming]
• [x] Added passing UI tests (including committed .stderr file)
• [x] cargo test passes locally
• [x] Executed cargo dev update_lints
• [x] Added lint documentation
• [x] Run cargo dev fmt

---

changelog: new lint: [direct_recursion]

Fixes https://github.com/rust-lang/rust-clippy/issues/428

After we're done with this, I'll open a follow-up issue for the indirect recursion lint

[felix91gr]

@PLeVasseur WIP.

I think the implementation is correct. I'll complete the documentation later, hopefully this weekend ^^

[PLeVasseur]

Nice! Thanks for taking on the implementation.

[felix91gr]

Hey @felix91gr -- thanks for writing this up. One thing I was unclear on: should this lint also check for recursion that's due to macros or only functions?

Well... since it's a LateLintPass, then I believe it should already be linting macro-generated code by default. I wonder if there's a straightforward way of testing it :thinking: I'll give it a spin.

[felix91gr]

Sorry for the CI churn. It took me a while to understand why it was failing the changelog check.

[rustbot]

r? @samueltardieu

rustbot has assigned @samueltardieu. They will have a look at your PR within the next two weeks and either review your PR or reassign to another reviewer.

Use r? to explicitly pick a reviewer

[rustbot]

:warning: Warning :warning:

• There are issue links (such as #123) in the commit messages of the following commits. Please move them to the PR description, to avoid spamming the issues with references to the commit, and so this bot can automatically canonicalize them to avoid issues with subtree.
  • 30beb9536f0d8a8c027e5ceecf207224522aa836

[felix91gr]

⚠️ Warning ⚠️

* There are issue links (such as `#123`) in the commit messages of the following commits.
  _Please move them to the PR description, to avoid spamming the issues with references to the commit, and so this bot can automatically canonicalize them to avoid issues with subtree._
  
  * [30beb95](https://github.com/rust-lang/rust-clippy/commit/30beb9536f0d8a8c027e5ceecf207224522aa836)

I feel like this should be in the quick CI checks (like the changelog check), so that CI may do an early exit and avoid running the heavier test suites.

[felix91gr]

Something that I'd like to add in a later PR, is a link to the Safety Critical Coding Guidelines where recursion is addressed.

Currently the functions section is empty, but I hope to get working on filling it as soon as I can https://coding-guidelines.arewesafetycriticalyet.org/coding-guidelines/functions.html

[felix91gr]

This doesn't flag all potentially direct recursive calls. For example, it doesn't trigger on this code path:

fn recurse_through_var(x: i32) -> i32 {
    let call = if x < 10 {
        std::convert::identity
    } else {
        recurse_through_var
    };
    call(x - 1)
}

Should I add this caveat to the documentation?

Context:

That kind of indirect call through a variable is ultimately undecidable (as a consequence of constprop being undecidable). That being said, one can attempt to detect as many of those cases as one can (as most lints that touch on undecidability do).

But still, this kind of detection requires MIR machinery that we don't have (in particular, it requires dataflow analysis capable of doing non-lexical constant propagation). I might implement it with the help of some friends in the future, but for now doing this properly in Clippy would require me to implement it in Clippy... which is outside of the scope of this lint.

See also: the transmute-null-ptr-to-ref lint. When I implemented it, I stopped at the base cases due to the same lack of dataflow machinery.

[felix91gr]

@samueltardieu does that make sense? I hope that makes sense.

Basically, I don't want to implement variable-bound-recursion-detection without the necessary dataflow machinery; it's going to be a pain and it's going to be a lot less complete than it would be otherwise.

It should probably be noted somewhere in the lint docs that this implementation only touches direct fn call expressions.

I could open up an issue as well noting down the code paths that a more sophisticated recursion analysis could catch, and write down exactly what such a lint is currently blocked on.

[samueltardieu]

I've opened a FCP for this lint.

[felix91gr]

I'll quickly revert this to a draft PR, because I most certainly have unfinished work here

[felix91gr]

Done for today. Assuming I'm catching all the cases we talked about in Zulip, I still have 2 more things to do:

1. Change the my_enclosing_body_owner usage so that the iterator is used directly in the check_expr function. This should make it a little bit more efficient.
2. Add the attribute that I have marked as #<TODO> in the documentation.

[felix91gr]

This should now be feature complete. However, the way I'm checking for the marker attribute allowed_recursion is not efficient. I'll probably implement a custom visitor so that it stops walking the AST as soon as it sees it.

[felix91gr]

Visitor implemented. Now this should be way more efficient than it was a couple hours ago :)

[felix91gr]

Uh oh, the lint just crashes with zero_copy! Damn, good to know.

[felix91gr]

Okay, the source of those panics should be gone now. In a local test, something made serde_yaml crash, but I don't think it was my changes. Well, CI will probably tell us if it was.

[felix91gr]

Edit: sorry, I had a brain fart and thought I'd found a false negative for the lint.

Draft mode again. I'm not linting this case:

enum Tree {
    Leaf(i32),
    Node(Box<Tree>, Box<Tree>),
}

fn sum_tree(tree: &Tree) -> i32 {
    match tree {
        Tree::Leaf(val) => *val,
        Tree::Node(left, right) => sum_tree(left) + sum_tree(right),
    }
}

[felix91gr]

Drat. I'm an idiot. I AM linting this case. It's just that I have two very similar working directories, one of them for indirect recursion, and that one hasn't been updated to match method calls... :facepalm:

[felix91gr]

Okay, this I think is an actual counterexample

trait RecSum {
    fn rec_sum(n: u32) -> u32;
}

struct Summer;

impl RecSum for Summer {
    fn rec_sum(n: u32) -> u32 {
        if n == 0 { 0 } else { n + Self::rec_sum(n - 1) }
    }
}

[felix91gr]

Solved the counterexample, and ditched the custom Visitor for a more traditional structure, which let me use typeck again c:

I think.... this is done now? We'll see.

[samueltardieu]

I had a quick initial review there.

Also, this is not linted while it should:

struct T(u32);

trait W {
    fn f(&self);
}

impl W for T {
    fn f(&self) {
        if self.0 > 0 {
            self.f()
        }
    }
}

[samueltardieu]

Also you should store DefId in the vector, and use .contains() to do lookups instead of explicit loops.

[samueltardieu]

You can probably remove all the matching against ExprKind::Call(…): when it contains a QPath::Resolved, it will be matched later on, and you can move the QPath::TypeRelative test on its own ExprKind::Path(QPath::TypeRelative(..)). Forget about ExprKind::Call altogether.

(this will also remove any duplicate for free since you won't match for calls)

[samueltardieu]

You can look at the review-direct-recursion branch in my fork to see what I am suggesting. See for example https://github.com/samueltardieu/rust-clippy/commit/ae065a38ca1a61b20f9dfd5cfd0e5d91326e7888

[felix91gr]

Also you should store DefId in the vector,

Ah, you're right. In prior iterations, I was doing the conversion the other way around so I was fine with keeping a stack of LocalDefIds. Now that I'm doing the conversion towards DefIds, they should absolutely be stored like that from the get-go.

and use .contains() to do lookups instead of explicit loops.

Yeah, no, you're absolutely correct.

[felix91gr]

You can probably remove all the matching against ExprKind::Call(…): when it contains a QPath::Resolved, it will be matched later on, and you can move the QPath::TypeRelative test on its own ExprKind::Path(QPath::TypeRelative(..)). Forget about ExprKind::Call altogether.

(this will also remove any duplicate for free since you won't match for calls)

That makes sense. I continued this topic in the Zulip because it has been brought up multiple times, and I feel like the Zulip is a better place to have a conversation about that.

[felix91gr]

I'm still solving this failing test:

struct T(u32);

trait W {
    fn f(&self);
}

impl W for T {
    fn f(&self) {
        if self.0 > 0 {
            self.f()
        }
    }
}

[felix91gr]

I fixed the case above, but I'm not entirely sure why I need both of these branches to capture default Trait implementations v/s non-default implementations:

ExprKind::MethodCall(_, _, _, _) => {
    let typeck = cx.typeck_results();
    if let Some(basic_id) = typeck.type_dependent_def_id(expr.hir_id) {
        // This finds default Trait implementations of methods
        if self.fn_id_stack.contains(&basic_id) {
            span_lint(cx, DIRECT_RECURSION, expr.span, "this method contains a call to itself");
        }
        // Whereas this finds non-default implementations
        else if let args = typeck.node_args(expr.hir_id)
            && let Ok(Some(fn_def)) = Instance::try_resolve(cx.tcx, cx.typing_env(), basic_id, args)
            && let type_resolved_def_id = fn_def.def_id()
            && self.fn_id_stack.contains(&type_resolved_def_id)
        {
            span_lint(cx, DIRECT_RECURSION, expr.span, "this method contains a call to itself");
        }
    }
},

Like, it would make a lot of sense to me if I had to always follow the second branch. But for some reason, this test doesn't pass without the first one:

// Case 8: Linting on Default Trait Method Implementations //
// Here we check that recursion in trait methods is also captured by the lint
trait MyTrait {
    fn myfun(&self, num: i32) {
        if num > 0 {
            self.myfun(num - 1);
            //~^ direct_recursion
        }
    }
}

[felix91gr]

At the ExprKind::Path(QPath::Resolved(_, path)) => { branch there's still something I'd like to do, which is to give different messages depending on if I've matched an associated function call or not. Next push will probably address that.