User-defined patterns, on things which are not enums

How can I place a (zero-overhead) pattern-match syntax on something that's not actually an enum? For instance, say I have a struct T(i32), and I want to pattern match for positive/negative values on it, like

match x {
  T::Pos => foo(),
  T::Neg => bar(),
}

being syntactic sugar for

match x {
  if x > 0 { foo() } else { bar() }
}

This is a relatively common feature in FP languages (in OCaml it can be done with a ppx, in Haskell with extension PatternSynonyms I believe).

I imagine this can be done with a macro, but is there language support for this? I'm a beginner in rust so I'm not quite comfortable writing macros yet :stuck_out_tongue: Regardless, what would be the lightest way (in terms of syntax) to accomplish it? Thanks!


PS: Perhaps here is a better example. Let struct NonzeroOption(u64). Then

match x { Some(x) => foo(x), None => bar() }

as syntactic sugar for

if x != 0 { foo(x.0) } else { bar() }

that is, an option type for a non-zero u64 without any memory overhead, which can be used in the same way as a regular option, including exhaustivity checks in pattern matching.

In general, since guards can’t be part of patterns in Rust, even with macros you can’t create too many interesting kinds of custom patterns. You’d have to stick to API such as the pre-PatternSynonyms API for Data.Sequence, i.e. provide view functions that return enums.

For the concrete case of ranges of integers, you can however work with range patterns.

struct T(i32);

macro_rules! negative {
    () => {
        T(i32::MIN..=-1)
    };
}
macro_rules! positive {
    () => {
        T(1..=i32::MAX)
    };
}
macro_rules! zero {
    () => {
        T(0)
    };
}

fn fun(x: T) {
    match x {
        negative!() => {}
        positive!() => {}
        zero!() => {}
    }
}

Not a perfect solution of course since those macros will only work as long a that field is visible. So you might prefer the “view function” approach

struct T(i32);

enum Sign {
    Negative,
    Zero,
    Positive,
}

impl T {
    fn sign(&self) -> Sign {
        match self.0 {
            i32::MIN..=-1 => Sign::Negative,
            0 => Sign::Negative,
            1..=i32::MAX => Sign::Negative,
        }
    }
}

fn fun(x: T) {
    match x.sign() {
        Sign::Negative => {}
        Sign::Zero => {}
        Sign::Positive => {}
    }
}
1 Like

Thanks! The view function approach is actually fine from an ergonomics point of view, but how could I assure that it has no overhead? With a macro (for example to apply over the whole match) at least I have the assurance that it will get rewritten to exactly that code, and will not for example allocate a "view type" object which is immediately matched (this is not a problem for unit variants but see e.g. my second example).

PS: I'm coming from ocaml where the syntax is very lightweight, just match%view x with Pos -> foo() | Neg -> bar, which means "apply the view macro onto the whole match construct", which is in turn a sort of "super-macro" that based on the type of x dispatches to the corresponding macro which will rewrite into whatever expression, or error out if the type doesn't have a view implementation.

No overhead? Probably only possible by looking at the assembly, or benchmarking, or so. Otherwise, it’s a thing that relies on optimizations, so you can never be completely sure just how close to actually zero the overhead is.

Compared to typical garbage-collected functional programming languages, the algebraic data types of Rust (i.e. enum types) are very lightweight since their values just live on the stack, so there’s no boxing allocating+deallocating involved in creating an intermediate enum value. Thus even the worst-case possible overhead of creating an intermediate enum (when optimization doesn’t manage to eliminate it) is really quite small. Of course size of overhead is always relative to the size of the operation you compare it against. In a tight loop, when performance matters, you should probably double-check that your view functions and intermediate enums didn’t create unwanted overhead.

E.g. an enum without fields would be represented as simple integer value, existing in some register for a short time. The main overhead one needs to worry about might be the view function itself; make sure that it’s inlined (in particular across crate boundaries, where this might require an #[inline] attribute).


I’m not really familiar with ocaml and wasn’t able to – from your short description alone – understand the situation there you’ve been describing, with “view macro”s and the like.

I am familiar with Haskell, and for pattern synonyms in Haskell, last time I checked, those had some sketchy (not optimal) interaction with exhaustiveness checks for example; this is just one detail that I wanted to mention to keep in mind when theorizing about support for comparable features in Rust, since Rust is much more strict about match expressions being exhaustive than Haskell’s case … of expressions are.

2 Likes

I'm wondering why you need this. It seems way more confusing than useful… your NonzeroU64 example doesn't demonstrate anything, either, since Option<NonZeroX> has the same size as X due to niche optimization. There is no special syntax needed to support that kind of optimization.

Thanks for your answers! I've been some more reading (I'm still a rust noob), played around a little bit on godbolt, and I think that the best answer in my case might be to just have a "view" function that transforms my "actual" data type into an enum which reprents the "logical" data type (if that makes sense), and tag that view function with #[inline], thus ensuring that match x.view() { A => ..., B => ... } is inlined to something of the form match (if ... then { A } else { B }) {A => ..., B => ...}. This increases the chances that the compiler is able to optimise this to get rid of the intermediate enums.

To clarify, here is a link which I think illustrates what I mean with a much more realistic example: Compiler Explorer. I'm pleased to notice that the code for the example* functions is exactly the same as for the example*_baseline "manual" versions! I'm still not 100% satisfied in that this relies on optimisations which are in no way guaranteed to happen x)

In particular this is for a core data structure in a high-performance project I'm attempting to write, therefore here I really do want to squeeze the maximum performance and memory efficiency possible and I'm definitely obsessive about doing things the sub-optimal way.

You've probably already been told this a bunch of times, but humans are notoriously bad at reasoning about runtime performance so the best way to proceed is by making measurements and doing experiments.

It'd be really annoying to spend 5 or 6 hours trying to optimise this sort of pattern matching only to realise it doesn't improve performance because a) the compiler already optimises it properly, or b) the speed of your pattern matching is irrelevant because you're doing random memory access and spend all your time waiting on RAM (cachegrind is really a good tool for detecting those sorts of issues).

Also, make sure you do macro-benchmarks instead of micro-benchmarks (i.e. benchmark the entire system instead of a single function). As a general rule, the only thing micro-benchmarks are good for is putting your thing at the top of a list so you can win internet points.

Unless this is all for fun and educational purposes, in which case, have at it!

2 Likes

Ahaha, right now it's only for fun and educational purposes, trying to teach myself Rust and high-performance programming.

But in general, HPC code and systems programming requires the use of these micro-optimisations, therefore Rust must let the user customise the precise memory layout of her types, when required. The good think about Rust is that I can hide the messy unsafe internals in a nice safe interface, thus combining high-performance with developer ergonomics and safety.

Oh, and thanks for telling me about cachegrind, I had no idea that tool existed (though I believe perf can also profile cache misses).

That's called #[repr(C)] and it doesn't require custom pattern matching.

1 Like