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:

Details

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?