# structural equality

## 1 Status quo

Constants can be used in patterns as long as they implement the `StructuralEq` trait which means that they have *structural equality*.

A value has structural equality if it is equal to another value of the same type if and only if both values have the same *structure*. The structure of a value is either what's used by pattern matching for exhaustiveness checking (pattern matching) or what's observable during ctfe (const generics). A type has structural equality when all values of that type have structural equality.

Both in patterns and in const generics, we structurally compare values by converting the value to a value tree, represented using [`Valtree`] for const generics (it's currently less clear for pattern matching). Converting a value to a value tree ignores padding and the address of references.

Some values cannot be converted to a value tree, most notably raw pointers[^1], and unions[^2]. Other values could have structural equality but it would disagree with its `PartialEq` impl, e.g. `floats` (`0.0` and `-0.0`).

The `StructuralEq` trait is shallow. A type may implement `StructuralEq` even though one of its fields does not. `StructuralEq` is automatically derived if you derive `PartialEq` and `Eq`. On stable, it is not possible to explicitly implement these traits.

### 1.1 Pattern matching

Using a constant in a pattern is allowed, as long as its value has structural equality. The constant participates in exhaustiveness checking:

const ZERO: u32 = 0;

fn main() {
    match 3 {
        ZERO => println!("nothing"),
        1.. => println!("something"),
    }
}

The compiler therefore has to check whether the value of the constant has structural equality. It is always required that the type of the constant implements `StructuralEq` (which is only shallow). We then have to prove that all fields of the constant have structural equality. There are two ways to do this:
- The types of all fields also recursively implement `StructuralEq`, proving that all values of this type have structural equality. This check only needs the type of the constant.
- Given the value of the constant, all used fields (so only the used enum variants) have structural equality. This check requires the value of the constant and is relevant for [this example](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=2181ba6a3734f8eb984a5a95a371d9c6). This is currently computed using const qualification and has false negatives.

To not break the existing uses of constants without structural equality, the type-based check accepts constants with a nested field which only implement `PartialEq` and not `StructuralEq` as long as that field is behind a reference. If so, the pattern is structural up to that reference, and then uses the `PartialEq` impl of the pointee of the reference. If this happens we emit the `indirect_structural_match` future-compatibility lint.

// I am equal to anyone who shares my sum!
struct Plus(i32, i32);

impl PartialEq for Plus {
    fn eq(&self, y: &Self) -> bool { (&self.0+&self.1) == (y.0+y.1) }
}

impl Eq for Plus { }

const ONE_PLUS_TWO: & &Plus = & &Plus(1, 2);

fn main() {
    if let ONE_PLUS_TWO = & &Plus(3, 0) {
        println!("semantic!");
    } else {
        println!("structural!");
    }
}

These constants [cannot be used in `match` in const contexts](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=86b9e83d70ac651cec0158c040127b9b).

### 1.2 Const generics

Const generics requires constant values used to instantiate const parameters to have structural equality. The type system uses structural equality for type equality. Having values which are structurally equal while they can be differentiated by ctfe is therefore unsound as it can result in associated consts with different values for equal types.

To improve the general user-experience, we should restrict const parameter types to types which have structural equality, even if not strictly necessary. Alternatively, using a value without structural equality in the type system would have to immediately emit an error, which would also be sound.

As being usable as a const parameter type has backwards-compatibility concerns, this will probably require an explicit opt-in. See [project-const-generics#34](https://github.com/rust-lang/project-const-generics/issues/34).

## 2 Ideal state (according to @lcnr)

Constants used in pattern always use structural equality and participate in exhaustiveness checking. Structural equality means that the value gets compared by being converted to a `Valtree`. For constants without structural equality a match guard should be used: `FOO => ...` should instead be `val if val == FOO => ...`. The exact value of types with structural equality will therefore be part of the stability guarantees.

A type having structural equality should be explicit opt-in and also implementable if you have a manual `PartialEq` impl. `PartialEq` may for example use validity invariants or knowledge about layout of the type to speed the `eq` impl. See [this PR](https://github.com/rust-lang/rust/pull/75164) where using a manual impl of `PartialEq` required us to manually implement `StructuralEq`.

`StructuralEq` should be "deep" with trait system support. If `MyType: StructuralEq` holds, the type's fields should have structural equality, too. This is different from the current impls which don't say anything about the fields. The exact design of the `StructuralEq` trait can be found in the [appendix](https://hackmd.io/J3H6jwwQRw-MKTnTdX3zGw#Defining-the-StructuralEq-trait).

Const generics should only allow types which have such a "deep" `StructuralEq` impl.

We should not look at the value of constants used in patterns to decide how they are used. This would mean that we remove the check using const qualification. As an example: `Result<*const i32, i32>` as a type is not structurally equal, even if we could create `Err` values of it that can be compared. This is a breaking change, breaking [the example mentioned for the const qualification check](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=2181ba6a3734f8eb984a5a95a371d9c6).

## 3 Where to go

This ideal state is not achievable due to backward compatibility. We should allow constants which only implement `PartialEq` in patterns with a `deny`/`warn` by default lint. These then get treated as if they were used as a match guard and get compared using `PartialEq`.

A constant in a pattern therefore gets either fully destructured or stays completely opaque. This allows us to use [`Valtree`] for them.

[`Valtree`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/enum.ValTree.html

## Appendix

### Defining the `StructuralEq` trait

#[lang = "structural_eq"]
trait StructuralEq: Eq {}

`StructuralEq` is a **safe** trait. Implementations of the trait are checked by the compiler whether all fields also implement this trait, similar to impls of `Copy`. Unlike `Copy`, `StructuralEq` impls do not have to cover the whole type, so `impl StructuralEq for MyType<u32>` is allowed. Implementing `StructuralEq` for unions or extern types is forbidden by the compiler. With this it is guaranteed that `Valtree` creation for valid values if any type implementing `StructuralEq` never fails.

Implementing `StructuralEq` for a type `T` states the following:
- Stability guarantee that `T` will keep deep structural equality in the future.
- Structural equality is equivalent to semantic equality - `PartialEq::eq` - for `T`[^3]. Similar to `Eq`, this is **not** a safety invariant. Neither the compiler nor other code may rely on this for soundness.[^4]

The compiler may **not** replace calls to `PartialEq::eq` with structural comparisons, nor may it replace structural comparisons with calls to `PartialEq::eq`.

An incorrect `StructuralEq` impl may therefore only be surprising as for constants where the `PartialEq::eq` impl disagrees with structural equality may compare equal using `==` while not matching in a pattern. Equally, constants for which equality is not reflexive would not compare equal using `==` but would match in a pattern. While this may result in surprising behavior, it is not safety critical.

While changing the trait to be `unsafe` would allow the compiler to switch between structural and semantic equality, this does not seem like it's too usefull. Especially as `StructuralEq` should also be derivable, which is dangerous for unsafe trait.

## References

- https://github.com/rust-lang/rust/issues/74446

[^1]: We cannot look at the pointee, as it might not be initialized, and we cannot look at the address of the pointer as that one doesn't really exist during ctfe.
[^2]: We don't know which field is initialized and must not compare uninitialized memory.
[^3]: Which means that the `PartialEq::eq` impl has to adhere to the requirements of `Eq`, so we can use `Eq` as a supertrait without restricting the types for which `StructuralEq` can be implemented.
[^4]: Unless users treat `StructuralEq` as "`Eq`, but may be relied on for safety", I can't see where that would be helpful anyways. We shouldn't use `StructuralEq` as `unsafe trait Eq`, as types without structural equality can still correctly implement `Eq`.