Idea: Optics types, combining pattern types and view types

Here is a naive idea inspired by the optics (lens and prisms) in bidirectional transformation. Given the view types like lens that provides partial view and update for product types, and pattern types like prisms that provides partial view and update for sum types, the idea is to combine them together: the optics type that provides partial view and update for both product types and sum types.

Here is the syntax sketch.

struct Foo {
    x: i32,
    y: Bar,
}

enum Bar {
    A,
    B(i32),
    C {
        p: i32,
        q: i32,
    }
}

fn foo(
    // lens that views and updates x of Foo
    a: &mut optics_type!(Foo is .{ x, .. }),
    // prisms that views and updates Bar::B(_) of lens y of Foo
    b: &mut optics_type!(Foo is .{ y: Bar::B(_), .. }),
) {
    *a.x += 1;
    // `b.y` is guaranteed to be `Bar::B` so here it is exhaustive.
    let Bar::B(ref mut b) = b.y;
    *b += 1;
}

fn main() {
    let mut foo = Foo { x: 0, y: Bar::B(0) };
    foo(&mut foo, &mut foo);
}

With path-sensitive type checks (like that where we check if a field of a given type is moved), it is even possible to introduce prism types that can change the discriminant of an enum (but only allowed to use in function parameters).

// After calling this function, the discriminant of `c` is guaranteed 
// to be changed from `B` to `C`.
fn bar(c: &mut optics_type!(Bar is B(_) => C { .. })) {
    let Bar::B(b) = c;
    *c = Bar::C { p: b, q: b };
}
1 Like

Do you have any ideas on how this might be implemented. Does it involve unsafe wrapped in a safe interface? Could you give some details?

That being said, it looks like an interesting proposal.

as far as i can see, your proposal is "just" view types + pattern types, so it is unclear why a new optics_type! compiler macro should be necessary.

of course neither feature is close to stabilization so it is rather hard to tell what may or may not be possible, but it is true that it is important to make sure that they do work together

First, introduce new subtyping rules: (for convenience, write $ty is $pat as optics_types!($ty is $pat), $ty1 <: $ty2 as $ty1 is the subtype of $ty2).

  • for product types: (T1, T2) <: (T1, T2) is (_, ..), i.e. types that view more fields are subtype of types that view less fields.
  • for sum types: Option<T> is Some(_) <: Option<T>, i.e., the types that specify more strict discriminants are subtype of types that specify less strict discriminants.

Patterns in the optics types will be used for pattern exhaustiveness analysis. Subtyping conversion results are recorded during type checking and used for borrow check later.

Then, add new type rules for expressions:

  • the type of an integral literal expression carries that const pattern, e.g. the type of 42i32 is i32 is 42.
  • the type of an enum constructor is the pattern type with that discriminant, e.g. the type of Some(0i32) is Option<i32> is Some(0).

After that, add a new rule of borrow checking: for each mutable-mutable, or mutable-immutable borrow conflict pair reported by the original borrow checker, visit their subtyping conversion results, and check if their patterns overlap, and only report those where their patterns overlap as errors.

Taking the same example:

struct Foo {
    x: i32,
    y: Bar,
}

enum Bar {
    A,
    B(i32),
    C {
        p: i32,
        q: i32,
    }
}

We have:

  • Foo <: Foo is .{ x, .. }
  • Foo is .{ x: 0, .. } <: Foo is .{ x, .. }
  • Foo <: Foo is .{ y: Bar::B(_), .. })
  • Bar is B(_) <: Bar
  • Foo is .{ y: Bar::B(_), .. }) <: Foo is .{ y, .. }

The struct expression Foo { x: 0, y: Bar::B(0) } has type Foo is .{ x: 0, y: Bar::B(0) }. Then foo(&mut foo, &mut foo) does such type transformations:

    foo(&mut foo, &mut foo)
 :  fn(&mut Foo is .{ x: 0, y: Bar::B(0) }, &mut Foo is .{ x: 0, y: Bar::B(0) })
<:  fn(&mut Foo is .{ x: 0, .. }, &mut Foo is .{ y: Bar::B(0) })
<:  fn(&mut Foo is .{ x, .. }, &mut Foo is .{ y: Bar::B(_) })

which finishes type checking.

At borrowck, &mut foo, &mut foo are reported at first by the original borrowck (the NLL checker or Polonius), but they are converted to &mut Foo is .{ x, .. }, &mut Foo is . { y: Bar::B(_) } where their patterns don't overlap, so they will not be reported as borrow errors.

Here optics_type! is just a randomly picked name for combined view types and pattern types.

This sort of guaranteed update is mixing in a separate issue. Obviously Bar is B(_) | C { .. } could change the discriminant. Guaranteeing such a change, though, is much more difficult because of how it interacts with unwinds.

Consider the following function bar and a sample call.

// After calling this function, the discriminant of `c` is guaranteed 
// to be changed from `B` to `C`.
fn bar(c: &mut optics_type!(Bar is B(_) => C { .. })) {
    let Bar::B(b) = c;
    *c = Bar::C { p: b, q: b };
}

fn main() {
    let mut c = Bar::B(0);
    bar(&mut c);
}

A possible solution is to ascribe different subtypes when the function call bar returns and unwinds.

fn main() -> () {
    let mut _0: ();
    let mut _1: Bar;
    let _2: ();
    // Subtyping info of variables are not recorded here,
    // but are recorded via a special statement `AscribeSubtype`
    // to support path-sensitive subtypes.
    let mut _3: &mut Bar;
    scope 1 {
        debug c => _1;
    }

    bb0: {
        _1 = Bar::B(const 0_i32);
        // After assignment, discriminant of `_1` becomes `B`.
        AscribeSubtype(_1, Bar::B(0_i32));
        _3 = &mut _1;
        // Before calling `bar`, the discriminant of `*_3` is `B`.
        AscribeSubtype(*_3, Bar::B(_));
        _2 = bar(copy _3) -> [return: bb1, unwind bb2];
    }

    bb1: {
        // When `bar` returns, the discriminant of `*_3` becomes `C`.
        AscribeSubtype(*_3, Bar::C { .. });
        return;
    }

    bb2: {
        // When `bar` unwinds, the discriminant of `*_3` becomes `B | C`,
        // as we don't know whether its discriminant has changed
        // at the point of panicking.
        AscribeSubtype(*_3,  Bar::B(_) | Bar::C { .. });
        continue;
    }
}

What I'm still not sure is, when should the subtype checking should be done.

  • on the one hand, it is path sensitive and should involve unwinding paths, it'd be better to check at MIR before borrowck.
  • on the other hand, the pattern exhaustiveness analysis depends on the results of subtyping checks, then it'd be better to check at THIR before that.

There can also be some variations of optics_type!(Bar is B(_) => C { .. }):

Type Before called After returns (Output) After returns (Residual) After unwinds
optics_type!(Bar is B(_) => C { .. }) B(_) C { .. } C { .. } B(_) | C { .. }
optics_type!(Bar is B(_) |=> C { .. }) B(_) B(_) | C { .. } B(_) | C { .. } B(_) | C { .. }
optics_type!(Bar is B(_) ?=> C { .. }) B(_) C { .. } B(_) | C { .. } B(_) | C { .. }
optics_type!(Bar is B(_) !=> C { .. }) B(_) C { .. } C { .. } C { .. }

where ?=> only applies to functions returning impl Try.

I think the case that's hardest is the following:

// After calling this function, the discriminant of `c` is guaranteed 
// to be changed from `B` to `C`.
fn bar(c: &mut optics_type!(Bar is B(_) => C { .. })) {
    let Bar::B(b) = c;
    assert_ne!(b, 101);
    *c = Bar::A;
    assert_ne!(b, 42);
    *c = Bar::C { p: *b, q: *b };
}

fn do_things(val: i32) {
    let mut c = Bar::B(val);
    panic::catch_unwind(panic::AssertUnwindSafe(|| {
        bar(&mut c);
    }));
    // What are the allowed values of `c` here?
}

I see two possible problems to fix up (but there could be more):

  1. c is set to Bar::A temporarily. This could simply be banned by the optics_type! macro, because that's not an allowed discriminator on input or output.
  2. c can still be Bar::B(_) after the call to bar, because bar can panic before it changes *c. This one doesn't have an easy answer; either you need to confirm that c must change to Bar::C (and cannot change back) before any panics can happen, or you require that the input state is also a valid output state (i.e. bar has to become fn bar(c: &mut optics_type!(Bar is B(_) => B(_) | C { .. }))).

Note that there is also some demand for accurate "can panic" tracking for other use cases; the fact that there's no compiler-level solution yet implies to me that this is one that's only easy to solve in simple cases like the example above.

1 Like

Haskell implements it them using Van Laarhoven functors [1]

In Rust you can get pretty close to emulating them with GATs, composition and all. 100% safe code, just doing all sort of cursed type level magic. I have a somewhat working proof of concept sitting somewhere.

  1. Control.Lens.Type
1 Like

I see two possible problems to fix up (but there could be more):

Regarding here:

There can also be some variations of optics_type!(Bar is B(_) => C { .. }):

Type Before called After returns (Output) After returns (Residual) After unwinds
optics_type!(Bar is B(_) => C { .. }) B(_) C { .. } C { .. } B(_) | C { .. }
optics_type!(Bar is B(_) |=> C { .. }) B(_) B(_) | C { .. } B(_) | C { .. } B(_) | C { .. }
optics_type!(Bar is B(_) ?=> C { .. }) B(_) C { .. } B(_) | C { .. } B(_) | C { .. }
optics_type!(Bar is B(_) !=> C { .. }) B(_) C { .. } C { .. } C { .. }

where ?=> only applies to functions returning impl Try.


  1. c is set to Bar::A temporarily. This could simply be banned by the optics_type! macro, because that's not an allowed discriminator on input or output.

Agreed.

  1. c can still be Bar::B(_) after the call to bar, because bar can panic before it changes *c. This one doesn't have an easy answer; either you need to confirm that c must change to Bar::C (and cannot change back) before any panics can happen, or you require that the input state is also a valid output state (i.e. bar has to become fn bar(c: &mut optics_type!(Bar is B(_) => B(_) | C { .. }))).

In my opinion: if bar returns, treat c like &mut optics_type!(Bar is B(_) => C { .. }), and if bar panics, treat it like &mut optics_type!(Bar is B(_) => B(_) | C {.. }).


fn do_things(val: i32) {
    let mut c = Bar::B(val);
    panic::catch_unwind(panic::AssertUnwindSafe(|| {
        bar(&mut c);
    }));
    *// What are the allowed values of \`c\` here?*
}

As for this, I think it should not be allowed to capture a variable into a closure of a type which discriminant set may shrink or change, i.e., captured variables can never have types like &mut optics_type!(Bar is B(_) => C { .. }) or &mut optics_type!(Bar is B(_) | C { .. } => B(_)), but can only have types like &mut optics_type!(Bar is B(_) => B(_) | C { .. }) or &mut optics_type!(Bar is B(_) | C { .. }).

What I expect is, during typeck, the type of &mut c should be inferred as:

fn do_things(val: i32) {
    let mut c = Bar::B(val);
    let _: optics_type!(Bar is B(_)) = c;
    panic::catch_unwind(panic::AssertUnwindSafe(|| {
        let _: optics_type!(Bar is B(_)) = c;
        bar(&mut c);
        let _: optics_type!(Bar is C { .. }) = c;
    }));
    let _: optics_type!(Bar is B(_) | C { .. }) = c;
}

The inferred results should be similar even without catch_unwind:

fn do_things(val: i32) {
    let mut c = Bar::B(val);
    let _: optics_type!(Bar is B(_)) = c;
    let mut _closure = || {
        let _: optics_type!(Bar is B(_)) = c;
        bar(&mut c);
        let _: optics_type!(Bar is C { .. }) = c;
    };
    // let _: optics_type!(Bar is B(_) | C { .. }) = c;
}

It is because we cannot predict whether or when the closure will be executed, nor whether it will have panicked at all after execution.

That, in turn, means that the following is not legal code, and needs semantics defined - does the call to double always panic? Does it fail to compile because bar has a hidden allowed return of Bar::B?:

// After calling this function, the discriminant of `c` is guaranteed 
// to be changed from `B` to `C`, except on a panic, where it might be `B`.
fn bar(c: &mut optics_type!(Bar is B(_) => C { .. })) {
    let Bar::B(b) = c;
    assert_ne!(b, 101);
    *c = Bar::A;
    assert_ne!(b, 42);
    *c = Bar::C { p: *b, q: *b };
}

fn double(c: &mut optics_type!(Bar is C { .. } => C { .. })) { {
    let Bar::C { p, q } = c;
    Bar::C { p: p * 2, q: q * 2 }
}

fn do_things(val: i32) {
    let mut c = Bar::B(val);
    panic::catch_unwind(panic::AssertUnwindSafe(|| {
        bar(&mut c);
    }));
    double(&mut c);
}

Note that, in the current compiler, whether bar can panic or not is not known at compile time (although people would love it if that were accurately known), and thus there is no way for this code to only error at compile time if a panic unwinds through bar; worse, while it's obvious in this case that there's a catch_unwind involved, once you get into interior mutability and threads, it's possible for the panic to be on another thread that has shared access to a Mutex<Bar> instead.

In general, you can get out of the worst of the pain of panics by declaring that the compiler won't verify the type of c until runtime, and will panic (or some other suitable runtime behaviour) if the type is wrong; I get the impression, though, that what you want is compile-time checking of both precondition and post-condition of the optics type (as that's what the work "guaranteed" implies to me) - if I'm wrong, I apologise for wasting your time on this.

This also implies that if you define optics_type! as semantically panicking if pre- or post-conditions are not met (so double is defined as panicking if, on input, the discriminant of c is not Bar::C, and panicking if, on output, the discriminant of c is not Bar::C), you've got something that works.

You can then, as a quality of implementation issue, have the compiler spot cases where a panic is guaranteed (e.g. let mut c = Bar::B(val); double(&mut c);) and error on them, and spot cases where a panic is likely and issue a warning.

Of course.

Here I have to restrict the type only applies to path-sensitive analysis. For example, in some MIR analysis path, when bar returns and jump to bb1 or unwinds and jump to bb2, we know that *c is C { .. } at the beginning of bb1 and *c is B(_) | C { .. } at the beginning of bb2.

I expect it fails to compile because c is captured in a closure (the compiler doesn't have to know the semantics of panic::catch_unwind, the only thing it has to consider is that, c is captured in the closure || { bar(&mut c) } where bar can change c's discriminant from B to C, but it cannot assume when or whether the closure will be called. Therefore:

  • at // 1, c is known to have the discriminant of B.
  • at // 2, c is captured into the closure, and its discriminant remains unchanged (still B).
  • at // 3, bar returns (if it unwinds, the control flow will be different and will go to somewhere doing some cleanups), we know that c's discriminant becomes C by bar.
  • at // 4, out of the closure, since c may be changed from B to C in the closure, but we're not sure when or whether the closure will be called, so we only knows that c's discriminant can be B | C when the closure's lifetime ends. (Note that, we don't have to know what panic::catch_unwinds internally, and change it to any other functions, e.g. iter::from_fn, the compilation result will not change either.)
  • given that double requires a Bar with discriminant C, but we've only got c with discriminant B | C, so we now have enough information to report a compile error.
fn do_things(val: i32) {
    let mut c = Bar::B(val);
    // 1
    panic::catch_unwind(panic::AssertUnwindSafe(|| {
        // 2
        bar(&mut c);
        // 3
    }));
    // 4
    double(&mut c);
}

The possible compile error might be:

error: mismatched types
  --> SOURCE.rs:LL:CC
   |
LL |    panic::catch_unwind(panic::AssertUnwindSafe(|| {
   |                                                -- first, `c` is captured as type `Bar::B(_)` ...
LL |        bar(&mut c);
   |        ----------- then, `c`'s type has changed to `Bar::C { .. }` ...
LL |    }));
   |    - so discriminant of `c` may change after the closure being called 
LL |    double(&mut c);
   |            ^^^^^^ expected `Bar::C { .. }`, found `Bar::B(_) | Bar::C { .. }`
help: when or whether the closure will be called is unknown at compile time

What you're doing there by saying that the closure can't capture c is effectively ad-hoc analysis to say that "this code can't panic and unwind", and it becomes quite complex to implement - because it's not enough to say that "a value of type &mut Bar cannot be captured by a closure", but instead you have to say that you cannot capture either a value of type &mut T where T has an element of type Bar or &mut Bar, or a value of type &T where there's interior mutability around something that contains a Bar.

And the "element of type Bar" bit is going to be painful to implement - right now, if the fields of Foo are private, the only thing that needs to be exposed to callers is that Foo has a certain size and alignment requirement. You now need to expose that Foo might contain a problematic value for optics types, and generate the error if Foo is captured by a closure - since there might be methods in Foo that depend on the guarantees of optics types on Bar, but where your closure allows a panic to be "caught" (catch_unwind, std::thread::spawn etc) and then breaks the guarantees you expected would be true.