The `unconditional_recursion` lint can trigger in divergent functions

[wesleywiser]

@eddyb noticed these cases:

pub fn foo(x: bool) { // WARN function cannot return without recurring
    if x {
        foo(x);
    } else {
        loop {}
    }
}

Try It

pub fn foo(x: bool) { // WARN function cannot return without recursing
    if x {
        foo(!x);
    } else {
        panic!("foo");
    }
}

Try It

@eddyb thinks the way to resolve this is to reimplement the lint on top of the dataflow analysis stuff.

https://discordapp.com/channels/442252698964721669/443151243398086667/492702651759329280

[estebank]

Isn't the first one kind of correct, if misleading? The second one is indeed problematic.

[cramertj]

// WARN function cannot return without recursing

Technically correct, because it can't return at all ;)

[eddyb]

@estebank It's wrong because the function can diverge without recursively calling itself.
They're both literally the same example, I just replaced one form of divergence with another.

[estebank]

@eddyb mmmm....

In my mind I read this as

pub fn foo(x: bool) { // Ret
    if x {
        foo(x);  // Ret
    } else {
        loop {}   // `!`, can't return
    }
}

while the latter, being panic! it is also !, but can terminate (while the loop has no side-effects).

You're correct, but I'd love it if we could somehow differentiate when evaluating divergence between "can't return" and "can't return but can panic".

[eddyb]

@estebank Both "stuck in an infinite loop" and "panics" are different from "infinitely self-recurses".

What we want to detect is unguarded self-recursion, that is, when you forgot to check some condition that would give you a convergent or divergent "base case", that would stop the infinite recursion.

The message of the lint doesn't help my point, it should be more clearly about "infinite recursion".

While usually you're missing a condition, or you're calling the wrong function, it's also possible that you're using infinite recursion to infinitely repeat something - but we don't have guaranteed tail calls, so what you really want to do is rewrite the infinite recursion into an infinite loop.

[steveklabnik]

Triage: no change

[jonas-schievink]

Since we currently lint this:

fn inf() {
    inf();
    loop {}
}

Wouldn't this need a backwards dataflow analysis to catch this case? It doesn't looks like the bit would ever be propagated to a return block like this. A backwards analysis would instead propagate it to the entry block, if I understand correctly.

[eddyb]

@jonas-schievink You're right, there's no merge for either the panic!(...) or the loop {} examples, that could collect the information.

Presumably we want to tell these apart:

fn inf() {
    match foo() {
        0 => inf(),
        1 => inf(),
        _ => inf(),
    }
}

vs

fn inf() {
    match foo() {
        0 => inf(),
        1 => loop {},
        _ => inf(),
    }
}

So I guess the property you'd propagate backwards is "always reaches self-call", which means every block starts at false (except those that contain a self-call) and the merge operator is &.

The funny thing about this being a 1-bit-per-block analysis is that instead of a BitMatrix you can use a simple BitSet<BasicBlock> and fixpoint is also easier to achieve. Rough sketch:

let mut results = BitSet::empty(body.basic_blocks());
let mut queue: VecDeque<_> = self_calls.iter().collect();
while let Some(bb) = queue.pop_front() {
    if results.contains(bb) {
        // Already propagated.
        continue;
    }

    let always_reaches_self_call = match body[bb].terminator.kind {
        TerminatorKind::Call(..) if self_calls.contains(bb) => true,

        TerminatorKind::SwitchInt(branches)
            => branches.iter().all(|&target| results.contains(target)),

        TerminatorKind::Goto { target }
        // ... and all other single target variants, ignoring any cleanup edges
            => result.contains(target),

        // We only ever go backwards through the CFG, these should be impossible to hit.
        TerminatorKind::Return | TerminatorKind::Resume => unreachable!(),
    };

    if always_reaches_self_call {
        // This is a newly confirmed-to-always-reach-self-call block.
        assert!(results.insert(bb));

        // Propagate backwards through the CFG.
        queue.extend(body.predecessors(bb));
    }
}
let fn_always_reaches_self_call = results[START_BLOCK];