Clippy hangs forever for long "if" logical condition

[charles-wangkai]

Summary

> cargo clippy -V
clippy 0.1.71 (8ede3aae 2023-07-12)

Clippy hangs forever for the following code with a long "if" logical condition.

Reproducer

I tried this code:

fn main() {}

fn search(visited: &mut [[bool; 7]], r: usize, c: usize) -> i32 {
    if (r != 0
        && !visited[r - 1][c]
        && r != 6
        && !visited[r + 1][c]
        && (c == 0 || visited[r][c - 1])
        && (c == 6 || visited[r][c + 1]))
        || (c != 0
            && !visited[r][c - 1]
            && c != 6
            && !visited[r][c + 1]
            && (r == 0 || visited[r - 1][c])
            && (r == 6 || visited[r + 1][c]))
    {
        return 0;
    }

    todo!()
}

I expected to see this happen:
Finish quickly.

Instead, this happened:
Hangs forever.

Version

rustc 1.71.0 (8ede3aae2 2023-07-12)
binary: rustc
commit-hash: 8ede3aae28fe6e4d52b38157d7bfe0d3bceef225
commit-date: 2023-07-12
host: x86_64-apple-darwin
release: 1.71.0
LLVM version: 16.0.5

Additional Labels

No response

[y21]

It gets stuck here

rust-clippy/clippy_lints/src/booleans.rs

Line 374 in c0bdb3d

for simple in Bool::Not(Box::new(expr)).simplify() {

Seems to be taking quite a while to simplify expressions. There's a comment a few lines above saying that it has exponentially slow behavior and it links to #825, which looks quite similar to the issue here.

[blyxyas]

This is a known issue, with an issue filed oli-obk/quine-mc_cluskey#2. I would fix it if I had access to the paper, but it's behind a paywall.