exhaustiveness checking hangs forever when compiling pulsar-rs

[xxchan]

git clone https://github.com/streamnative/pulsar-rs
cd pulsar-rs
cargo +nightly check

Then it hangs forever

bisect leads to ee80c8d
cc @Nadrieril @cjgillot

searched nightlies: from nightly-2023-11-26 to nightly-2023-11-29
regressed nightly: nightly-2023-11-27
searched commit range: f5dc265...6cf0888
regressed commit: ee80c8d

bisected with cargo-bisect-rustc v0.6.7

Host triple: aarch64-apple-darwin
Reproduce with:

cargo bisect-rustc --start 2023-11-26 --script ./test.sh 

bisect script:

#!/bin/sh

set -ex

timeout 40s cargo check

[apiraino]

@xxchan thanks for the report! Do you think you can help in producing a bit smaller reproducible of this issue? That would be great to build a test case and help the debugging.

Note: compiling the entire project will eat all the memory available

@rustbot label +E-needs-mcve +I-compilemem

[Nadrieril]

I minimized it to this giant match statement, which still depends on the generated protobuf types. I'm working on reducing further

[Nadrieril]

Minimized to this:

struct BaseCommand {
    ack: bool,
    ack_response: bool,
    active_consumer_change: bool,
    add_partition_to_txn: bool,
    add_partition_to_txn_response: bool,
    add_subscription_to_txn: bool,
    add_subscription_to_txn_response: bool,
    auth_challenge: bool,
    auth_response: bool,
    close_consumer: bool,
    close_producer: bool,
    connect: bool,
    connected: bool,
    consumer_stats: bool,
    consumer_stats_response: bool,
    end_txn: bool,
    end_txn_on_partition: bool,
    end_txn_on_partition_response: bool,
    end_txn_on_subscription: bool,
    end_txn_on_subscription_response: bool,
    end_txn_response: bool,
    error: bool,
    flow: bool,
    get_last_message_id: bool,
    get_last_message_id_response: bool,
    get_or_create_schema: bool,
    get_or_create_schema_response: bool,
    get_schema: bool,
    get_schema_response: bool,
    get_topics_of_namespace: bool,
    get_topics_of_namespace_response: bool,
    lookup_topic: bool,
    lookup_topic_response: bool,
    message: bool,
    new_txn: bool,
    new_txn_response: bool,
    partition_metadata: bool,
    partition_metadata_response: bool,
    ping: bool,
    pong: bool,
    producer: bool,
    producer_success: bool,
    reached_end_of_topic: bool,
    redeliver_unacknowledged_messages: bool,
    seek: bool,
    send: bool,
    send_error: bool,
    send_receipt: bool,
    subscribe: bool,
    success: bool,
    tc_client_connect_request: bool,
    tc_client_connect_response: bool,
    unsubscribe: bool,
}

fn request_key(command: BaseCommand) {
    match command {
        BaseCommand {
            subscribe: true, ..
        } => {}
        BaseCommand {
            partition_metadata: true,
            ..
        } => {}
        BaseCommand {
            partition_metadata_response: true,
            ..
        } => {}
        BaseCommand {
            lookup_topic: true, ..
        } => {}
        BaseCommand {
            lookup_topic_response: true,
            ..
        } => {}
        BaseCommand { producer: true, .. } => {}
        BaseCommand {
            producer_success: true,
            ..
        } => {}
        BaseCommand {
            unsubscribe: true, ..
        } => {}
        BaseCommand { seek: true, .. } => {}
        BaseCommand {
            close_producer: true,
            ..
        } => {}
        BaseCommand { success: true, .. } => {}
        BaseCommand { error: true, .. } => {}
        BaseCommand {
            consumer_stats: true,
            ..
        } => {}
        BaseCommand {
            consumer_stats_response: true,
            ..
        } => {}
        BaseCommand {
            get_last_message_id: true,
            ..
        } => {}
        BaseCommand {
            get_last_message_id_response: true,
            ..
        } => {}
        BaseCommand {
            get_topics_of_namespace: true,
            ..
        } => {}
        BaseCommand {
            get_topics_of_namespace_response: true,
            ..
        } => {}
        BaseCommand {
            get_schema: true, ..
        } => {}
        BaseCommand {
            get_schema_response: true,
            ..
        } => {}
        BaseCommand { send: true, .. } => {}
        BaseCommand {
            send_error: true, ..
        } => {}
        BaseCommand {
            send_receipt: true, ..
        } => {}
        BaseCommand {
            active_consumer_change: true,
            ..
        } => {}
        BaseCommand { message: true, .. } => {}
        BaseCommand { flow: true, .. } => {}
        BaseCommand {
            redeliver_unacknowledged_messages: true,
            ..
        } => {}
        BaseCommand {
            reached_end_of_topic: true,
            ..
        } => {}
        BaseCommand { ack: true, .. } => {}
        BaseCommand {
            close_consumer: true,
            ..
        } => {}
        BaseCommand {
            auth_challenge: true,
            ..
        } => {}
        BaseCommand { connect: true, .. } => {}
        BaseCommand {
            connected: true, ..
        } => {}
        BaseCommand { ping: true, .. } => {}
        BaseCommand { pong: true, .. } => {}

        _ => {}
    }
}

[Nadrieril]

What surprises me is not that this hangs exhaustiveness checking, it's that it worked before #117611 x)

[Nadrieril]

Ah no I get why. Well this is literally the worst case scenario for exhaustiveness. It's going through the 2^number_of_fields possibilities to determine which arms are reachable

[Nadrieril]

This is terrible, I think the premise of #117611 might be fully broken :'(

[Nadrieril]

Well, a related case hangs on stable too: playground

At that point we're hitting the fact that exhaustiveness is NP-hard, so occasional exponential behavior is unavoidable.

[xxchan]

Do you think practically it's better to rewrite such code to workaround this issue?

[Nadrieril]

It's definitely a case that stretches the limits of what we can handle. If the struct only had 20 fields it would compile fine.

I do think this is a reasonable case though. I intend to revert my PR if I can't find a better solution

[apiraino]

hey folks, thanks for digging deep into this. Let me know if it would be useful to loop in the compiler team. I can nominate this issue and have them have a look at the next meeting (tomorrow Thu. 30th)

[Nadrieril]

I think we'd only need their help if this requires an emergency revert/backport. Do you happen to know how long we have before this makes it into beta?

[apiraino]

If I read this page correctly, the next beta cut will be on Dec, 20th

[Nadrieril]

Ok that's perfect, thanks for figuring this out. Gives me enough time to figure out a proper solution

[estebank]

@Nadrieril regardless of whether the current algorithm is kept (tweaked) or reverted, it'd be nice if we could somehow detect "the number of match arm conditions is high too high" and have an eager warning for it to gently nudge people away from it.

[Nadrieril]

Oh yeah, good idea! That would make everyone's life much easier. I have an idea of how to detect that

[Nadrieril]

I found a fix! I'll let #118308 get reviewed first because it would conflict; I'll submit a PR after that

[apiraino]

WG-prioritization assigning priority (Zulip discussion).

Also, it does not reproduce on the latest beta, so it's a nightly regression.

@rustbot label -I-prioritize +P-high -E-needs-mcve

[Nadrieril]

To avoid cases like this in the future I'm thinking of adding a resource counter to exhaustiveness checking, so we can abort with a clear message instead of hanging. I know rust-analyzer wants that too.

[Nadrieril]

Fix is up, if anyone can merge it before the beta cutoff: #118796

[Nadrieril]

@apiraino the beta cutoff date is approaching, do you know the procedure in a case like this? #118796 is not trivial, it could be introducing new bugs. Would it make sense to wait for beta cutoff, merge #118796, and if no bug is revealed after a week or two we backport it?

[apiraino]

@Nadrieril yeah I agree to first ensure #118796 is reviewed, then we can always backport it.

thanks for that patch!