Confusing errors regarding types and lifetimes

This piece of code is relatively similar to the piece of code I am trying to fix.
Have been working on this for hours, and not getting anywhere, any help would be super appreciated.

playground link

fn foo<A>(
    f1: impl Fn(&str) -> Result<(&str, A), ()>,
    base: &str,
    f2: impl Fn(A) -> bool
) {
    let s: String = base.to_owned();
    let option = Some(s.as_ref());
    let mapped = option.map(f1);
    let r = mapped.unwrap();
    let (rem, prod) = r.unwrap();
    assert!(f2(prod));
    assert_eq!(rem.len(), 0);
}


fn main() {
    fn bar<'a>(s: &'a str) -> Result<(&'a str, &'a str), ()> {
        Ok((&s[..1], &s[..]))
    }
    
    
    fn baz(s: &str) -> Result<(&str, &str), ()> {
        Ok((&s[..1], &s[..]))
    }
    
    foo(bar, "string", |s| s.len() == 5); // fails to compile
    
    foo(baz, "string", |s| s.len() == 5); // fails to compile 
}

This type:

impl Fn(&str) -> Result<(&str, A), ()>

will connect the lifetime on the two string slices to each other, and leave the A type not connected to that lifetime. This means that it does not allow functions where A might contain references into the provided string slice.

// The second output depends on the input. Fails to compile!
fn bar<'a>(s: &'a str) -> Result<(&'a str, &'a str), ()> {
    Ok((&s[..1], &s[..]))
}
// The second output is independent of the input. Compiles!
fn bar2<'a>(s: &'a str) -> Result<(&'a str, &'static str), ()> {
    Ok((&s[..1], "Hello World!"))
}

Would something like this work for you?

fn foo<A: ?Sized>(
    f1: impl Fn(&str) -> Result<(&str, &A), ()>,
    base: &str,
    f2: impl Fn(&A) -> bool
) { ... }

playground

Unfortunately, i don't think so. The core of my problem is that I'm not able to specify the lifetime parameter for A, which should match the lifetime bound that is generated by the higher range trait bound that is desugared by impl Fn(&str) -> Result<(&str, A), ()> as the type for f1. I honestly think this is a compiler bug of some kind. after desugaring, foo becomes

fn foo<F1, A, F2>(
    f1: F1,
    base: &str,
    f2: F2
) 
where
    F1: for<'s> Fn(&'s str) -> Result<(&'s str, A), ()>,
    F2: Fn(A) -> bool
{...}

It seems to me that in cases where A would be parametric over 's as defined in for<'s>, no matter how hard I try I cannot find a way to bind A's lifetime parameter to 's. These cases include when A is &str or any struct/enum that would contain &str, where &str references the same str as the arument to f1.

Well, you are right, you can't bind A to the higher ranked bound. The type A is defined outside of the for<'s> ... expression, so 's is not available to the type A. You should keep in mind that changing a lifetime parameter on a type yields a new, distinct type.

Based on recommendations from a number of people here, on the internals thread I made, and on stack overflow I changed my code to simplify it by using a wrapper trait.

playground


trait Parser<'s> {
    type Output;
    
    fn call(&self, input: &'s str) -> (&'s str, Self::Output);
}

impl<'s, F, T> Parser<'s> for F
where F: Fn(&'s str) -> (&'s str, T) {
    type Output = T;
    fn call(&self, input: &'s str) -> (&'s str, T) {
        self(input)
    }
}

fn foo<F1, F2>(
    f1: F1,
    base: &'static str,
    f2: F2
) 
where 
    F1: for<'a> Parser<'a>,
    F2: FnOnce(&<F1 as Parser>::Output) -> bool
{
    // These two lines cannot be changed.
    let s: String = base.to_owned();
    let str_ref = s.as_ref();
    
    let (remaining, produced) = f1.call(str_ref);
    assert!(f2(&produced));
    assert_eq!(remaining.len(), 0);
}

struct Wrapper<'a>(&'a str);

fn main() {
    fn bar<'a>(s: &'a str) -> (&'a str, &'a str) {
        (&s[..1], &s[..])
    }
    
    fn baz<'a>(s: &'a str) -> (&'a str, Wrapper<'a>) {
        (&s[..1], Wrapper(&s[..]))
    }
    
    foo(bar, "string", |s| s.len() == 5); // fails to compile
    
    foo(baz, "string", |s| s.0.len() == 5); // fails to compile 
}

this code generates an internal compiler error currently:

error: internal compiler error: src/librustc_infer/traits/codegen/mod.rs:61: Encountered error `OutputTypeParameterMismatch(Binder(<[closure@src/main.rs:45:24: 45:40] as std::ops::FnOnce<(&<for<'a> fn(&'a str) -> (&'a str, &'a str) {main::bar} as Parser<'_>>::Output,)>>), Binder(<[closure@src/main.rs:45:24: 45:40] as std::ops::FnOnce<(&&str,)>>), Sorts(ExpectedFound { expected: &str, found: <for<'a> fn(&'a str) -> (&'a str, &'a str) {main::bar} as Parser<'_>>::Output }))` selecting `Binder(<[closure@src/main.rs:45:24: 45:40] as std::ops::FnOnce<(&&str,)>>)` during codegen

thread 'rustc' panicked at 'Box<Any>', src/librustc_errors/lib.rs:875:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

note: the compiler unexpectedly panicked. this is a bug.

note: we would appreciate a bug report: https://github.com/rust-lang/rust/blob/master/CONTRIBUTING.md#bug-reports

note: rustc 1.43.0 (4fb7144ed 2020-04-20) running on x86_64-unknown-linux-gnu

note: compiler flags: -C codegen-units=1 -C debuginfo=2 --crate-type bin

note: some of the compiler flags provided by cargo are hidden

error: aborting due to previous error

error: could not compile `playground`.

To learn more, run the command again with --verbose.

I will be making a bug report as suggested, thank you everyone for your help so far.

See #71955

For anyone who reads through this later on and wonders if I ever found a workaround, I did!

This workaround involves placing the state referenced by the function calls into a Context structure. Because of the current issues with Higher Rank Trait Bounds (HRTBs), this workaround avoids them entirely. Instead, we refactor object initialization (which could be expensive) into the Context's constructor. The context completely owns the function state. This is fine though, since the function only needs a reference to that state, not ownership. Whenever we need to call the function, we pass it to the Context's call function, which ensures that the lifetime of the arguments to the function and it's output matches the lifetime of the context in/on which it runs.

playground

// Workaround code: the state of the function is placed 
// into a struct so that all of the references are valid
// for the lifetime of of &self. This way concrete lifetimes
// can be used because all lifetimes start on the function 
// call, rather than several statements into the function. 
//
// This work around eliminates the need for Higher Ranked 
// Trait Bounds (HRTBs), since all lifetimes are instantiated
// on function initialization.

struct Wrapper<'a>(&'a str);

struct ParserContext {
    inner: String
}

impl ParserContext {
    fn new(base: &str) -> Self {Self {inner: base.to_owned()}}
    
    fn call<'a, O>(
        &'a self, 
        f1: fn(&'a str) -> (&'a str, O),
        f2: fn(O) -> bool,
    ) {
        let (remaining, produced) = f1(self.inner.as_str());
        assert_eq!(remaining.len(), 0);
        assert!(f2(produced));
    }
}


fn main() {
    fn bar(s: &str) -> (&str, &str) {
        (&s[..0], &s[..])
    }
    
    fn baz(s: &str) -> (&str, Wrapper) {
        (&s[..0], Wrapper(&s[..]))
    }
    
    
    // I tried to extract the section below into its
    // own function previously (foo) but this would
    // always inevitably fail because of lifetime issues.
    // this work around only adds one line of code to the calling
    // function to create the context to hold the state 
    // used by the functions passed to `call`, so this 
    // is an acceptable, and rather eloquent work around.
    let pc = ParserContext::new("string");
    
    pc.call(bar, |s| s.len() == 6);
    pc.call(baz, |s| s.0.len() == 6);
}
1 Like

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.