Parser caches are unsound, in their current form

[zesterer]

The parser cache API is unsound today because it does not require that Cached::Parser<'src> is covariant over 'src (which is required for the lifetime downcast to be sound).

Note, for potential readers: this does not mean that your usage of the API is unsound today: this is an edge case.

Consider:

use std::cell::RefCell;

use chumsky::cache::{Cache, Cached};

fn main() {
    let x = Demo {
        x: RefCell::new(None),
    };
    let c = Cache::new(x);

    {
        let s = String::from("demo");

        *c.get().x.borrow_mut() = Some(&s);
    }

    let y = *c.get().x.borrow();
    dbg!(y);
}

struct Demo<'r> {
    x: RefCell<Option<&'r String>>,
}

impl<'r> Cached for Demo<'r> {
    type Parser<'src> = Demo<'src>;

    fn make_parser<'src>(self) -> Self::Parser<'src> {
        Demo {
            x: RefCell::new(None),
        }
    }
}

(thanks @_madfrog)

MIRI gives:

error: Undefined Behavior: constructing invalid value at .<enum-variant(Some)>.0: encountered a dangling reference (use-after-free)
  --> src\main.rs:17:13
   |
17 |     let y = *c.get().x.borrow();
   |             ^^^^^^^^^^^^^^^^^^^ Undefined Behavior occurred here
   |
   = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior
   = help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html for further information

Potential solutions

One potential solution is to require implementers of Cached to provide an implementation of the following method:

fn to_smaller<'a, 'big: 'small, 'small>(x: &'a Self::Parser<'big>) -> &'a Self::Parser<'small>;

This method would be invoked before a downcast (to ensure that an implementer does not simply stub it via todo!() or similar) as proof that the downcast were legal.

However, this comes with the disadvantage that &dyn Parser does not currently work with such an approach.

Fallback

If no good solution can be found, the cache API should be removed. Since it is currently under the unstable feature flag, this is not a semver violation.