Traits for short-circuiting || and &&

[est31]

Problem statement

I propose addition of two traits And and Or for making the && and || operators overrideable.

Motivation, use-cases

It would be worth to do it for consistency reasons: the other operators can be overridden, too. IIRC && and || are the only operators for which there isn't at least an unstable trait yet.

For usage of && in c++ one can check grep.app, same for ||.

Solution sketches

Generally, I would suggest following the conventions laid down by the other traits in std::ops. The function names inside the traits all seem to contain the trait name, e.g. BitAnd has a bitand function, Div has a div function. This is useful because if you have implemented multiple op traits on some type you can just do div and you know that there is no conflict with another trait. Thus, I would suggest also putting the trait name into all And and Or functions.

The names And and Or come from Rust's internal representation, where they get called the same (AST does not distinguish & and &&, here && is just two And's, but HIR has BitAnd and And, as does MIR). This is in distinction to BitAnd which is &. Note that the way proc_macro exposes && and || is through Punct so there is no stable API that already exposes a name for &&.

The current behaviour of && and || on bool exposes short-circuiting behaviour, so if the left hand side is false, && does not evaluate the right hand side, and if it is true || does not evaluate the right hand side. In order to make it possible for bools to use the traits, and allow users to customize it, a simple trait with one function and or or is not enough, we need a second function to decide whether the right hand side should be evaluated at all.

I would propose the following design for And:

trait And<Rhs = Self> {
    type Output;
    type Intermediate;
    // gets called if and_should_eval_rhs returned Continue.
    fn and(this: Self::Intermediate, other: Rhs) -> Self::Output;
    // gets called before the and function to determine if there is a
    // short circuit or not.
    fn and_should_eval_rhs(self) -> std::ops::ControlFlow<Self::Output, Self::Intermediate>;
}

Or would be analogous. In the standard library, the two traits should be implemented on bool only (outside of tests).

Alternatively to rhs, we could also name it right, next or such. That there is already prior art in other binop traits via the Rhs generic parameter name, but of course that name is not subject to any stability guarantees.

let ret = foo().bar() && foo2().bar2()would be lowered to something like:

let ret = {
    let val = foo().bar();
    match And::and_should_eval_rhs(val) {
        ControlFlow::Continue(val) => And::and(val, foo2().bar2()),
        ControlFlow::Break(other) => other,
    }
};

The signature of and_should_eval_rhs takes self by-value to return it again so that self can be used in the Break case to construct Self::Output. This move-on-happy-path behavior might potentially be wasteful for larger types, but it's already an existing problem of Rust's operators, and adding yet another and_early_exit(self) -> Self::Output function would not be worth it. For large types, one can impl it on &mut BigType or &BigType instead, and use those instead.

On nightly, && chains belonging to if might contain let statements that might fail. Those will be represented as bools, so if someone wants let statements to work in their && chain, they need to implement And<Rhs=bool>.

Links and related work

Originally @scottmcm suggested making these trait-overrideable in zulip.

C++ has prior art via an operator &&, that is similarly implemented on bool. I'm not sure how short-circuiting is handled for non-bool return types.

What happens now?

This issue is part of the libs-api team API change proposal process. Once this issue is filed the libs-api team will review open proposals in its weekly meeting. You should receive feedback within a week or two.

[joshtriplett]

There have been past proposals for this.

One of the past proposals suggested a different approach, which I'd personally prefer. Rather than a separate and_should_eval_rhs method, just have and and or take a FnOnce closure for the right-hand side.

[est31]

I've tried looking for proposals in the past, but didn't find any. I re-did the search and now I found some:

• https://internals.rust-lang.org/t/pre-rfc-overload-short-curcuits/10460
• https://internals.rust-lang.org/t/a-different-way-to-override-and/14627
• Allow Overloading || and && rfcs#2722

The RFC proposes the trait to be implemented on more types than just bool, but for the trait, the RFC arrived at almost the same design, that's pretty nice.

Regarding closures, they seem to be discussed a bit in the RFC thread. Disadvantages I've found, both my own thoughts and ones I found in the RFC:

• How would you lower foo() && { if bar() { return false; } else { baz()} }? Closures can't influence control flow of the outer function. It's weird code but we still have to support it.
• It seems weird to me to move out parts of a function's body into a different function during lowering. That would conflict with someone's understanding of how a Rust program works. await does this too, but that's widely documented and has always been the case, instead of this being introduced to an existing construct. And it's required for await to work on a technical level too, here closures are not required.
• Closures would monomorphize the and function for every single && out there (unless you passed a dyn closure). In general, for bools you would want it to be inlined every single time, but one can think of implementations of and where you just want one copy and that's it.
• They would also return different output during backtrace printing.
• Closures still can't declare bindings for the outside context, as would be needed for let chains. You could create the bindings as MaybeUninit<Foo> at the start and then assign to them in the closure, but I think that's a bit of a hack. I think a closure-free design is better.
• Edit: there is also a quadratic buildup with closure parameters: If you have a chain like a.foo() && b.foo() && c.foo() && ... then there will be closures like Closure01 { b, c, d, e, ... }, Closure02 { c, d, e, ... }, Closure03 { d, e, ... }. In other words, in such chains with n elements, O(n) much data has to be moved around due to the desugaring (d,e,f etc are probably pointers as we don't have move closures here, but still).

[scottmcm]

Personally I think desugaring to closures is unacceptable for all the same reasons that we have ? and .await instead of monads: it's the only way to avoid the "what colour is my function" problem, and the only way to have move checking and such work properly.

---

This ACP still brings to mind a bunch of the same questions that I had in that RFC thread.

This loses information:

fn and_should_eval_rhs(self) -> std::ops::ControlFlow<Self::Output, Self>;

because it forces

fn and(self, other: Rhs) -> Self::Output;

to handle all of Self, not just the part that's actually possible.

Imagine implementing the trait for Option:

impl<T> LogicalOr for Option<T> {
    type Output = Self;
    fn or_should_eval_rhs(self) -> std::ops::ControlFlow<Self::Output, Self> {
        match self {
            Some(x) => Break(Some(x)),
            None => Continue(None),
        }
    }
    fn or(self, other: Rhs) -> Self::Output {
        match self {
            None => other,
            Some(x) => unreachable!(), // Why did I need to handle this?
        }
    }
}

Which makes me wonder if LogicalAnd and LogicalOr would make sense to share one trait, at least for part of it. If there's a fn should_short_circuit(self) -> ControlFlow<Short, Long>, then && and || just look at the different halves of it.

Notably, try { a?; b? } is the same a.and(b) on result, and thus arguably what a && b would do. So part of me wonder if it would make sense to be the same method as Try::branch...

This probably needs a bunch of examples of implementations that people would want to use with this, in order to better figure out which parts need to be parameterized (like whether we'd only have Option<T>: LogicalOr or also Option<T>: LogicalOr<T>).

The IRLO thread had a long conversation about what people even thought the semantics of things should be. So that might give an interesting place to start from: https://internals.rust-lang.org/t/pre-rfc-overload-short-curcuits/10460/58?u=scottmcm.

[est31]

Good point about the signature being inflexible. I guess there is need for a type Intermediate; after all...

About sharing traits, idk. You might be able to share them, but I think beyond ability there should be a strong reason for the sharing, e.g. a desire that the traits all have to work similarly. I'd argue that consistency with the existing std::ops traits would be nice. Right now these traits stay close to syntax, and don't share anything even if they could. E.g. the Sub trait is theoretically not necessary as it can be built from the Neg and Add traits. And if you want to stretch it, a trait || might not be necessary at all as it can be built from Not and And traits, complicating the implementation for types like Option a lot, but for Result there is a very nice mapping.

As for which implementations of And and Or would be desireable, I think that should be a discussion of its own, to be had after one has overrideable && and || (stable or unstable). In general, I think the main pushback the RFC received (impressively negative upvote vs downvote ratio) was due to the suggested impls on Result and Option, not due to the ability to override && and || on its own. My personal reason why I think these traits should exist at all is consistency with the other operators (they have their own traits, too), not as a means to provide a sugar for unwrap_or_else or or_else. That can (or can not) be added later.

It's ultimately a separate question I think, outside of "how can we design the trait so that it supports possible implementations for X, Y, Z".

[programmerjake]

E.g. the Sub trait is theoretically not necessary as it can be built from the Neg and Add traits.

that doesn't actually work -- some types support sub but not neg nor add, e.g. mathematical sets can be subtracted (set difference), but can't be negated or added, instead the corresponding operations would be bitwise not (set complement -- not supported on most set implementations since they don't have universal sets) and bitwise or (set union)

[est31]

@programmerjake Fair points (except that set addition is a thing, the minkovski sum, but is a different thing in general). 👍

[est31]

Per @scottmcm 's reply, I have changed the proposal to include the Intermediate type. My proposal is now the same that RFC 2722 suggested, except for delegating the part where the trait is implemented for Option and Result for later.

[scottmcm]

I bring it up mostly because it seems to me like And::and isn't part of what && does today, and it's unclear to me whether it ought to exist at all. a && b being Option::zip instead of Option::and is something I bring up as an example for a reason that someone might want that.

a && b is just if let e @ false = a { e } else { b } today, no merge.

So if I were to replicate that for Option, just as an example, that same format works:

if let e @ None = a { e } else { b }

Thus to me the traits feel more like

trait LogicalAnd<RHS = Self> {
    fn logical_and(self) -> ControlFlow<RHS>;
}

with a desugaring like a && b →

if let ControlFlow::Break(x) = LogicalAnd::logical_and(a) {
    x
} else {
    b
}

and the implementation for bool being the obvious

impl LogicalAnd for bool {
    fn logical_and(self) -> ControlFlow<Self> {
        if self { ControlFlow::Continue(()) }
        else { ControlFlow::Break(self) }
    }
}

(Which would exist for generic code, but not be called normally, just like impl Add for i32 and friends.)

Whereas having more than that needs to justify the existence of the merge function, especially since the order in which it runs gets quite unusual. ? needs to call branch and from_residual, but at least they're one after the other. With a && b && c && d && …, the call order seems like it'd end up being and_should_eval_rhs → and_should_eval_rhs → and_should_eval_rhs → and_should_eval_rhs → … → and → and → and → and.

[est31]

@scottmcm thanks for exploring the design space :).

a && b being Option::zip instead of Option::and is something I bring up as an example for a reason that someone might want that.

Good point that you can implement && for Option too. I don't want to discuss much about which types should get && and/or || support once the traits are there, but personally, I think that && has way less of a case to be implemented on Option than || does, as it's simply not worth the complexity it introduces. I have almost never needed Option::and, while doing a lot of unwrap_or_else in my life. Users who want to only implement || but not && obviously are going to require two separate traits at least. This last conclusion is why I put down this point at all, to add a point on your earlier questions whether there should only be one trait/function, maybe even just Try, or there should be multiple traits.

That being said, the trait should definitely support such an impl.

To give another example for where an and and or function would be useful, in the grep.app search I've linked above, you can find the pytorch example, which implements && on its own internal representation for expressions, to obtain quasi-quoting like semantics.

In Rust, such quasi-quoting is usually done via macros, which have the advantage of giving you spans, but maybe some folks might not need spans. In C++ there is way less choice obviously, as it doesn't have such a well-developed (non template) macro system as Rust has.

especially since the order in which it runs gets quite unusual.

Good point. I don't see a way out of such order weirdness. Even if you pass closures, eventually you'd have a step where the result is being passed upwards through the closure chain. However, similar nesting behaviour is seen today already, e.g. via drop order: let foo = foo(); let bar = foo.bar(); let baz = bar.baz(); drops in order drop(baz); drop(bar); drop(foo);.

[scottmcm]

I have almost never needed Option::and, while doing a lot of unwrap_or_else in my life.

I totally agree about this, but I'll emphasize that ? on Option serves the same flow as and, which makes the need for and that much less. I wonder if it'd make sense to have a core::option::coalesce! macro, or something, to target the opposite-of-? goal even more specifically, like SQL has.

That would have the advantage that coalesce!(foo(), bar(), continue) would plausibly be tolerable, whereas people seem to loathe foo() || bar() || continue (and it warns on bools today, despite compiling).

which implements && on its own internal representation for expressions

That looks like it's doing https://en.wikipedia.org/wiki/Expression_templates? That feels weak as motivation to me, because that's also a motivation for allowing </<=/==/!=/>=/> to return something other than bool, but we seem uninterested in doing that.

[joshtriplett]

It's not clear how this ended up as a libs ACP; this is a change to the language. The exact signatures of the traits, and the bikeshedding thereof, is the least of the things to be figured out there. (And I'm guilty of some of that bikeshedding myself, sorry.)

In addition to that:

• The previous RFC for this got postponed in favor of try, which still seems like the right answer for all the use cases it proposed.
• It's not obvious what other use cases exist beyond DSLs (for which we have macros).

If someone wants to pursue this, they'd need a lang RFC, with a very clear use case other than DSLs or Option/Result.