rust-lang/rust — pull request #15503 by pnkfelix (2014-07-07 17:37:43+00:00)
Title: New `deriving` that generates O(n) code for PartialOrd, Ord, etc.

Instead of generating a separate case (albeit trivial) for each of the N*N cases when comparing two instances of an enum with N variants, this `deriving` uses the strategy outlined here: https://github.com/rust-lang/rust/issues/15375#issuecomment-47994007

In particular, it generates code that looks more like this:

```rust
match (this, that, ...) {
(Variant1, Variant1, Variant1) => ... // delegate Matching on Variant1
(Variant2, Variant2, Variant2) => ... // delegate Matching on Variant2
...
_ => {
let index_tup = {
let idx_this = match this { Variant1 => 0u, Variant2 => 1u, ... };
let idx_that = match that { Variant1 => 0u, Variant2 => 1u, ... };
...
(idx_this, idx_that, ...)
};
... // delegate to catch-all; it can inspect `index_tup` for its logic
}
}
```

While adding a new variant to the `const_nonmatching` flag (and renaming it to `on_nonmatching`) to allow expressing the above (while still allowing one to opt back into the old `O(N^2)` and in general `O(N^K)` (where `K` is the number of self arguments) code generation behavior), I had two realizations:

1. Observation: Nothing except for the comparison derivings (`PartialOrd`, `Ord`, `PartialEq`, `Eq`) were even using the old `O(N^K)` code generator. So after this hypothetically lands, *nothing* needs to use them, and thus that code generation strategy could be removed, under the assumption that it is very unlikely that any `deriving` mode will actually need that level of generality.
2. Observation: The new code generator I am adding can actually be unified with all of the other code generators that just dispatch on the variant tag (they all assume that there is only one self argument).

These two observations mean that one can get rid of the `const_nonmatching` (aka `on_nonmatching`) entirely. So I did that too in this PR.

The question is: Do we actually want to follow through on both of the above observations? I'm pretty sure the second observation is a pure win. But there *might* be someone out there with an example that invalidates the reasoning in the first observation. That is, there might be a client out there with an example of hypothetical deriving mode that wants to opt into the `O(N^K)` behavior. So, if that is true, then I can revise this PR to resurrect the `on_nonmatching` flag and provide a way to access the `O(N^K)` behavior.

The manner in which I choose to squash these commits during a post-review rebase depends on the answer to the above question.

Fix #15375.