finding unreachable case clause on huge enum blows up compile time even it does not have guard clause

[KisaragiEffective]

Reproduction steps

1. checkout https://github.com/KisaragiEffective/scala-match-on-huge-enum or https://github.com/KisaragiEffective/match-on-huge-enum-sealed-trait
2. just compile

Problems

sbt:match-on-huge-enum> compile
[info] compiling 1 Scala source and 1 Java source to /private/tmp/scala-match-on-huge-enum/target/scala-2.13/classes ...
[warn] /private/tmp/scala-match-on-huge-enum/src/main/scala/Hello.scala:5:5: Cannot check match for unreachability.
[warn] The analysis required more space than allowed.
[warn] Please try with scalac -Ypatmat-exhaust-depth 40 or -Ypatmat-exhaust-depth off.
[warn]     h match {
[warn]     ^
[warn] 1 deprecation (since 2.13.0); re-run with -deprecation for details
[warn] two warnings found
[success] Total time: 163 s (02:43), completed Sep 17, 2023 10:14:55 PM

There are two issues.

1. Each occurrence of the match expression adds a few minutes (originally reported as "3 or 4 minutes") to compilation time, which is non-negligible.
2. The current (2.13.12) compiler implementation takes too long time to find unreachable case (exhaustiveness performance issue is split: #12874).

Notes

This is a performance problem: there is a case in real world.

One of them is in "Bukkit", a minecraft server, is providing API for plugging into Minecraft. It provides a class called Material, which corresponds in-game item or block per one-by-one. As of today, there are 1866 entries.

Upon profiling we saw that scala.tools.nsc.transform.patmat.PatternMatching$OptimizeMatchTranslator.exhaustive occupies ~85% of the CPU time (unreachableCase also does ~15%, that's another story).

A work-around is to simply avoid match on those enums (ours is avoided by https://github.com/GiganticMinecraft/SeichiAssist/commit/1ad23ea5d778192470c10a95e7049f0920adad42, but preferred to use match).

The above also applies to Scala 2's "pseudo" enum (sealed trait + object). Some how its shorter (on my machine, its about half) than Java's one (but still slow).

If the match has only wildcard arm (or annotate scrutinee with @unchecked, thank you @dwijnand) , it will not blow up.

[eed3si9n]

It seems like you're reporting two issues:

1. The current (2.13.12) compiler implementation does not consider that the match is exhaustive [even though] it has _ arm.

2. Each occurrence of match expression takes about 3 or 4 minutes to compile.

Update: I've edited the description and moved most of the text into "Notes" section.

[dwijnand]

I'll double-check when I get back to this, but isn't the match analysis skipped if you annotate: (h: @unchecked) match { ... }? I might still see if we can do better, but I'd say it's arguably acceptable to require that annotation when you have a family of 1866 children..

[KisaragiEffective]

Yes, it is!

[eed3si9n]

Would it make sense to short circuit exhaustiveness check when there is a plain wildcard as case? It might speed up compilation for lots of code with large-ish ADT.

[dwijnand]

That's the split off exhaustivity issue, and yes, it should. But for reachability it's not enough.

[eed3si9n]

The current (2.13.12) compiler implementation takes too long time to find unreachable case

Ah, I see. Thanks for the clarification.

[KisaragiEffective]

We can skip (or, at least use lite algorithm) for finding unreachables if all of following conditions are met:

• the all patterns are either "plain" or disjunction of them
• there's no pattern with guard
• if it has wildcard, then it must cover at least one variant
• all variants are declared as final (always hold for Java ones and object whose super type is sealed trait types)
• ~~the match do not have duplicated variant (the latter of two case VariantX => /* ... */ would be reported as a unreachable)~~

Edit: attached some examples

Examples

val opt: Option[Int] = external()

// OK, there's no unreachable (useless).
i match {
    case _ => 0
}

// OK, there's no unreachable (also useless).
i match {
    case anyVariant => 0
}

// OK
i match {
    case Some(_) => 0
    case None => 1
}

// OK
i match {
    case Some(_) => 0
    case _ => 1 // this covers None
}

// OK (field of ADT can appear in arm body)
i match {
    case Some(x) => x,
    case None => 0
}

// OK (pattern can be disjunction)
i match {
    case Some(_) | None => 0
}

// Fallback (the field of ADT can not appear in guard)
i match {
    case Some(x) if x % 2 == 0 => x,
    case _ => 0
}

// Fallback (but it actually does not required to be falled-back)
i match {
    case Some(_) => 0,
    case Some(4) => 1, // unreachable
    case None => 2,
}

[KisaragiEffective]

I changed the title to be more accurately.

[SethTisue]

@dwijnand should we leave you assigned, do you intend to return to this?

[dwijnand]

I'm happy to stay assigned to it, but I'm not actively working on this.