Make the `unconditional_recursion` lint work across function calls

[jonas-schievink]

The lint for unconditional recursion currently only handles the case where a function calls itself directly, which means that many useful cases are missed:

• Undetected unconditional recursion in Clone impl using to_owned() #40437
• Stack overflow on cloning static boxed value with a generic impl #57633
• Rust stable, fatal runtime error: stack overflow, PartialEq #57299
• Stack overflow in fmt::Display impl #45838
• (+ lots of duplicates)

I've talked to @eddyb about this and it seems like they've come up with a workable solution that might also benefit other MIR passes:

IRC log

22:32 <eddyb> anyway, consider building a callgraph where you're only considering calls that are unconditional to some extent, i.e. if the function returns, they *must* have happened
22:32 <eddyb> then just fine cycles in it
22:32 <eddyb> *find
22:33 <eddyb> the current analysis is most likely that but limited to self-cycles
22:33 <jschievink> hmm, yeah. sounds like I need to determine postdominators then
22:33 <eddyb> jschievink: the monomorphization collector is actually perfect for this - or would be, if it recorded the source of a call :P
22:34 <eddyb> but, like, you do care about call targets post-Instance::resolve
22:34 <eddyb> (I just had an idea, heh)
22:34 <eddyb> (an optimization for the monomorphization collector)
22:36 <jschievink> so you want to run the lint on monomorphized MIR instead?
22:36 <eddyb> jschievink: the lint already kind of does this by taking parameters into account, it's just polymorphically doing it
22:37 <eddyb> ("monomorphized MIR" is not a thing that is actually stored anywhere, we monomorphize on the fly)
22:37 <jschievink> yeah, I didn't know the existing lint did that
22:37 <jschievink> it seemed so limited
22:38 <eddyb> I mean, all it does is it knows whether something can refer back to itself despite being a trait impl method
22:38 <eddyb> you only need to consider partial/full monomorphization if you look at the whole callgraph
22:38 <eddyb> to be able to construct it in the first place, I mean
22:39 <eddyb> basically you should "expand" callers of trait methods, transitively, until nothing actually can still hit trait dispatch
22:39 <eddyb> so it's actually the opposite of the collector, lol
22:40 <jschievink> wow
22:40 <eddyb> since you want to demand as little specificity as possible, while still ending up with a callgraph with only function bodies (and, well, dynamic dispatch)
22:41 <eddyb> so e.g. `foo<T>` calls `bar<Vec<T>>` and `bar<X>` calls `X::default()`
22:43 <eddyb> so you start with `<Self as Default>::default`, unknown `Self`, look at its callers (which hopefully is easy on a graph), and find that `Self` could be `X` of `bar<X>`
22:44 <eddyb> you recurse, with `bar<X>`, unknown `X`, and in its callers you find that `X` could be `Vec<T>` from `foo<T>`
22:45 <eddyb> therefore, `Self` could be `Vec<_>`, and that's the first type which is enough to resolve the implementation (of `<Vec<_> as Default>::default`)
22:46 <eddyb> this means that you can ignore the fact that `foo<T>` has even a million callers, all with different `T`, and not expand `bar` or `Default::default` further (especially since `Vec<T>: Default` doesn't require `T: Default`)
22:46 <eddyb> jschievink: this seems like a viable strategy for any callgraph-based analysis, not just infinite recursion lints
22:47 <eddyb> maybe someone should note it somewhere, before I forget :P
22:47  * eddyb does need to get back to work though
22:47 <jschievink> ah, so you could use the same approach in the collector?
22:49 <eddyb> jschievink: uhhhh
22:49 <eddyb> jschievink: the collector actually needs to monomorphize a million `foo`, `bar` and `<Vec<_> as Default>::default` (even if we might alleviate this in the future)
22:50 <eddyb> jschievink: hmm maybe you can do this collection in the forward direction too, with a bit of precomputation
22:53 <eddyb> jschievink: ah, no, it doesn't work forward because you'd need to actually gather the *transitive* set of callers
22:53 <eddyb> i.e. know that `foo<T>` calls `Vec<T>::default`, transitively
22:57 <jschievink> how would this analysis start, given that I need the call graph in the first place in order to find all callers of a method?
22:58 <eddyb> jschievink: at the end of the day, monomorphization wants to know all the static call targets (potentially ignoring some type parameters?), whereas this callgraph analysis thing wants to know all the definitions involved, with no finer granularity. they could be related but I have a hard time thinking about it
22:58 <eddyb> jschievink: you can build a callgraph that refers to `Default::default`
23:00 <jschievink> ah, so you'd build the callgraph "normally" and then expand references to trait methods?
23:00 <eddyb> you should mark it as unresolved though, to distinguish it from "default trait method body" (which has the same `DefId`)
23:00 <eddyb> jschievink: yupp
23:00 <eddyb> you'd build the callgraph fully generic, perhaps with Substs on the edges

[lcnr]

@rustbot claim

Will take a few weeks though.

edit: while I am still interested in this, I don't have the experience and time to implement this at the moment. In case someone else is motivated and wants to fix this, go ahead.