4 ms·

It's only NP-hard if you want the compiler to give you proper warnings/errors, right? As far as I know, the first matching arm is used. This means that if a com

It's only NP-hard if you want the compiler to give you proper warnings/errors, right? As far as I know, the first matching arm is used. This means that if a compiler doesn't do any analysis on it, but naively generates machine code to compare the value, then there is no complexity at all. (Not saying that that's acceptable...)

tialaramex 5y ago
Here's what Rust's compiler actually does today: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_build/thir/pattern/check_match/index.html https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_bu... Rust lets you say either "There are four specific possible Clowns, and I want everybody to explicitly deal with that" or you can write #[non_exhaustive] to say "There are several Clowns, right now I defined four of them, but maybe I'll add more some day" in which case you are allowed to only write code for those four Clowns, but everybody else is obliged by the compiler to handle the case with more Clowns than that since they can't depend on there only being four, and they have no idea how to name the additional ones that don't yet exist. So, a compiler that just punts is not a correct Rust compiler. It needs to do this analysis or it's compiling a different less useful language. In the real world the (default) exhaustive case is great for types that reflect some truth about the world being modelled, where you really do mean that all the code relying on this enumerated type should refuse to compile and needs re-engineering if your list is subsequently discovered not to really be exhaustive. Teapot not withstanding, there are definitely only five PlatonicSolids, such as Tetrahedron and Cube. The non-exhaustive case is great for types that reflect a truth you know or strongly suspect will change and everybody using your system needs to be prepared for that up front. In 2016 the enumerated list of US FederalHolidays didn't need Juneteenth, but in 2021 it does, we don't want random code to blow up because it had never imagined Congress would make new ones.
- EdSchouten 5y ago
  Sure. But a naive compiler whose only purpose is to stomp out a poorly optimized executable can safely ignore that annotation, right?
  - richardwhiuk 5y ago
    No, because checking that it is exhaustive is required by the language definition. It's not just not optimized, it's wrong.
  - kevincox 5y ago
    Yes, that annotation doesn't affect the codegen of a correct program (optimizations aside).
  - tialaramex 5y ago
    You could instead require everything to be treated as non-exhaustive in your cheap compiler. This means it would reject correct Rust code that explicitly handles each of the five PlatonicSolids differently, because that code lacks a way to handle a sixth (non-existent) PlatonicSolid. You can't just go "Eh, shrug emoji" without deciding what happens when you don't match. Suppose you silently treat the first (or last) handled case as the default, so I can write code that only handles Cubes and unlike the real Rust compiler your naive compiler spits out a program. But wait, now what happens for a Tetrahedron? I defined Cubes to have a 32-bit floating point size, but for whatever reason Tetrahedrons have a 16-bit integer length instead. Does your compiler just try to treat the 16-bit integer as a 32-bit floating point number since it assumes this was a Cube?
NieDzejkob 5y ago
It still needs to ensure that one of the arms will always match. (just not executing any branch in that case is tricky, because the arms can return values)
- remram 5y ago
  It does not need to check, if it assumes it. mrustc works that way, it is not trying to check code, only compile valid code: https://github.com/thepowersgang/mrustc https://github.com/thepowersgang/mrustc This is similar to C/C++'s " undefined behaviors". There are things you can write that aren't valid for the language, but that compilers are not required to catch.

tialaramex 5y ago

Here's what Rust's compiler actually does today: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_build/thir/pattern/check_match/index.html https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_bu... Rust lets you say either "There are four specific possible Clowns, and I want everybody to explicitly deal with that" or you can write #[non_exhaustive] to say "There are several Clowns, right now I defined four of them, but maybe I'll add more some day" in which case you are allowed to only write code for those four Clowns, but everybody else is obliged by the compiler to handle the case with more Clowns than that since they can't depend on there only being four, and they have no idea how to name the additional ones that don't yet exist. So, a compiler that just punts is not a correct Rust compiler. It needs to do this analysis or it's compiling a different less useful language. In the real world the (default) exhaustive case is great for types that reflect some truth about the world being modelled, where you really do mean that all the code relying on this enumerated type should refuse to compile and needs re-engineering if your list is subsequently discovered not to really be exhaustive. Teapot not withstanding, there are definitely only five PlatonicSolids, such as Tetrahedron and Cube. The non-exhaustive case is great for types that reflect a truth you know or strongly suspect will change and everybody using your system needs to be prepared for that up front. In 2016 the enumerated list of US FederalHolidays didn't need Juneteenth, but in 2021 it does, we don't want random code to blow up because it had never imagined Congress would make new ones.

EdSchouten 5y ago
Sure. But a naive compiler whose only purpose is to stomp out a poorly optimized executable can safely ignore that annotation, right?
- richardwhiuk 5y ago
  No, because checking that it is exhaustive is required by the language definition. It's not just not optimized, it's wrong.
- kevincox 5y ago
  Yes, that annotation doesn't affect the codegen of a correct program (optimizations aside).
- tialaramex 5y ago
  You could instead require everything to be treated as non-exhaustive in your cheap compiler. This means it would reject correct Rust code that explicitly handles each of the five PlatonicSolids differently, because that code lacks a way to handle a sixth (non-existent) PlatonicSolid. You can't just go "Eh, shrug emoji" without deciding what happens when you don't match. Suppose you silently treat the first (or last) handled case as the default, so I can write code that only handles Cubes and unlike the real Rust compiler your naive compiler spits out a program. But wait, now what happens for a Tetrahedron? I defined Cubes to have a 32-bit floating point size, but for whatever reason Tetrahedrons have a 16-bit integer length instead. Does your compiler just try to treat the 16-bit integer as a 32-bit floating point number since it assumes this was a Cube?

NieDzejkob 5y ago

It still needs to ensure that one of the arms will always match. (just not executing any branch in that case is tricky, because the arms can return values)

remram 5y ago
It does not need to check, if it assumes it. mrustc works that way, it is not trying to check code, only compile valid code: https://github.com/thepowersgang/mrustc https://github.com/thepowersgang/mrustc This is similar to C/C++'s " undefined behaviors". There are things you can write that aren't valid for the language, but that compilers are not required to catch.