I've wrote two equivalent functions in Rust, one compiles the other doesn't.

Program 1:

pub fn majority_element<T: Eq>(nums: &[T]) -> Option<&T> {
    nums.iter().fold(None, |acc, curr| {
        match acc {
            None => Some((1, curr)),
            Some((0, prev)) if prev != curr => Some((1, curr)),
            Some((count, prev)) => Some((count   if prev == curr { 1 } else { -1 }, prev)),
        }
    }).map(|(_, val)| val)
}

program 2 (doesn't compile)

pub fn majority_element<T: Eq>(nums: &[T]) -> Option<&T> {
    nums.iter().fold(None, |acc, curr| {
        match acc {
            None => Some((1, curr)),
            Some((0, prev)) if prev != curr => Some((1, curr)),
            Some((count, prev)) if prev == curr => Some((count   1, prev)),
            Some((count, prev)) if prev != curr => Some((count - 1, prev)),
        }
    }).map(|(_, val)| val)
}

error[E0004]: non-exhaustive patterns: `Some(_)` not covered
 --> src/lib.rs:3:15
  |
3 |         match acc {
  |               ^^^ pattern `Some(_)` not covered
  |

I prefer the second one because it expresses more clearly my intent.

Is this a compiler quirk or my pattern is actually not exhaustive? (and if so what am I missing?)
The type of acc is: Option<(usize, &T)>

CodePudding user response：

The compiler doesn't understand that either x == y or x != y, but for generic types this also can be false. I can create a type that returns false for both a == b and a != b fairly easily:

struct Evil;

impl PartialEq for Evil {
    fn eq(&self, _other: &Self) -> bool { false }
    fn ne(&self, _other: &Self) -> bool { false }
}

impl Eq for Evil {}

#[test]
fn test() {
    assert!(!(Evil == Evil));
    assert!(!(Evil != Evil));
}

Playground.

Such implementation violates the contract of PartialEq, as it requires that:

a != b if and only if !(a == b).

But it is still possible to write without unsafe code. That means that we can for example panic if this contract is violated, but we cannot cause undefined behavior. Unfortunately, non-exhaustive match can cause UB, and such is your case: if none of the arms matches you don't return any value from the function.

So the compiler not only does not, but also cannot rely on that. If you prefer, you can rewrite the code in the following way:

pub fn majority_element2<T: Eq>(nums: &[T]) -> Option<&T> {
    nums.iter()
        .fold(None, |acc, curr| match acc {
            None => Some((1, curr)),
            Some((0, prev)) if prev != curr => Some((1, curr)),
            Some((count, prev)) => match prev == curr {
                true => Some((count   1, prev)),
                false => Some((count - 1, prev)),
            },
        })
        .map(|(_, val)| val)
}