Add lint for direct recursive self-call of function

[huonw]

With trait objects it is not so rare to have code like

impl Foo for Box<Foo> {
    fn bar(&self, x: uint) {
        // call the `bar` method in the vtable, could try:
        // self.bar(x);
        // (*self).bar(x);
        // (**self).bar(x);
    }
}

One might first write self.bar(x), but this will be calling that same bar, via since Box<Foo> has a "real" bar method itself. The correct procedure is (**self).bar(x). This would helped by detecting the most obvious cases of a function calling itself in a nonterminating way. The most obvious way that is likely to have low risk of false positives is detecting if the CFG of a function reaches a self-call unconditionally. e.g.

// these receive a warning:
fn foo() { foo() }

fn bar(x: uint) {
    bar(x - 1);
}

fn baz(x: uint) -> uint {
    if x == 0 {
        println!("hi")
    }
    2 * baz(x + 1)
}

// this is fine:
fn qux(x: uint) {
    if x == 0 { loop {} } // (could be `return 1`, etc. etc.)

    qux(x - 1) + 1
}

Notably, it does not matter if the arguments to the self call are different, since the call will always occur, and it also does not matter if the self-call is in tail position.

There is the possibility that someone is using infinite recursion to achieve an infinite loop, it doesn't seem crazy to recommend that they use loop instead.

A more conservative alternative would be just detecting the method call in the first example, that is, a function that consists of a single expression that is a self-call.

[huonw]

I think an infinite loop written with tail recursion will be rare enough that that is not a problem.

[reem]

Personally I've hit a lot of infinite recursions caused by this, a lint would help a lot, especially since it's not really obvious how to fix the problem.

[emberian]

Me too!

[huonw]

I have this mostly implemented, except for some edge cases with loop {}, but the compiler doesn't seem to want to let me work out the precise method definition being called for a foo.bar() expression. (Meaning everything except the actual motivating example works.) I'm pestering anyone and everyone on IRC so we'll eventually find a solution...

[huonw]

Specifically, given

trait Foo {
    fn bar(&self); // A
}

impl Foo for uint {
    fn bar(&self) { // B
        self.bar(); // C
    }
}

I want to check if the method call C is calling method B, that is, obtain the DefId of the method called in the ExprMethodCall (if it exists, e.g. a method call on a trait object just optimisically assumes there isn't infinite recursion) and compare against the NodeId of B.

However, I can only work out how to obtain the DefId of A (via tcx.method_map and then ty::trait_item after pattern matching into the MethodTypeParam variant), and it's highly non-obvious how to correctly obtain the DefId of B. trans does obtain this info somehow, but naively copying its behaviour causes panics.

Advice, anyone?

[huonw]

Niko gave me a lot of advice on IRC.