E0597: How to track down spurious 'static bound

I've got an incorrect 'static bound in my codebase somewhere that I'm having trouble finding. The error message I'm getting is:

error[E0597]: `join` does not live long enough
   --> src/relation/peerjoin.rs:110:13
    |
110 |     let x = join.iter_all();
    |             ^^^^-----------
    |             |
    |             borrowed value does not live long enough
    |             argument requires that `join` is borrowed for `'static`
111 | //    assert_eq!(join.iter_all().count(), 3);
112 | } 
    | - `join` dropped here while still borrowed

I've already commented on the GitHub issue about the unhelpful error message. Auditing all mentions of static in the codebase doesn't turn up anything suspicious.

`git grep static` results
col.rs:pub trait Col: 'static
col.rs:/// The inner type must be `'static` and cannot take any generic
header.rs:pub trait Header: Sized + Clone + List + 'static {
header.rs:    /// Get a column reference; the type bound statically ensures it exists
record.rs:    col!{pub B: &'static str};
relation.rs:    fn explain(&'a self)->&'static str { std::any::type_name::<Self::Plan>() }
relation/subjoin.rs:impl<'a,Parent,Field,Child:'static> IntoIterator for &'a SubordinateJoin<Parent, Field> where 
relation/vec_opt.rs:pub struct CapacityErr(&'static str);

I suspect the problem is coming from an impl Trait or dyn Trait clause somewhere that is missing a lifetime annotation; is there a better way to track this down than auditing every instance of those in the codebase?

Some relevant code listings (I use #![feature(type_alias_impl_trait)] in this project):

`join` variable initialization
    let mut left: OpaqueRel<Vec<sexpr!{A,B,C}>> = Default::default();
    let mut right: OpaqueRel<Vec<sexpr!{C,B,D}>> = Default::default();

    left.insert(sexpr_val!{A(1),B(2),C(3)});
    left.insert(sexpr_val!{A(2),B(2),C(7)});
    left.insert(sexpr_val!{A(3),B(5),C(7)});

    right.insert(sexpr_val!{D(1),B(2),C(3)});
    right.insert(sexpr_val!{D(2),B(2),C(7)});
    right.insert(sexpr_val!{D(3),B(5),C(7)});

    let join = PeerJoin { left: left.as_ref(), right: right.as_ref() };
`iter_all` implementation
pub trait SelfQuery<'a>: RelationImpl + 'a {
    type Iter: 'a + Iterator<Item = Self::Item>;
    type Item: 'a + Record<Cols = Self::Cols>;
    fn iter_all(&'a self)->Self::Iter;
}

impl<'a,R> SelfQuery<'a> for R
where R:RelationImpl + 'a,
      &'a R: RealizedQuery<'a, R::Cols>
{
    type Iter = <&'a R as RealizedQuery<'a, R::Cols>>::Iter;
    type Item = <&'a R as RealizedQuery<'a, R::Cols>>::Row;
    fn iter_all(&'a self)->Self::Iter { self.execute() }
}
`RealizedQuery` implementation
/// A query result iterator
///
/// This is a wrapper around `IntoIterator` that verifies the returned items
/// are records that have an appropriate lifetime and header.
pub trait RealizedQuery<'a, Cols:Header> {
    type Iter: Iterator<Item = Self::Row> + 'a;
    type Row: 'a + Record<Cols = Cols>;
    fn execute(self)->Self::Iter;
}

impl<'a, Cols:Header, Q, Rec> RealizedQuery<'a, Cols> for Q
where Q:IntoIterator<Item = Rec> + 'a,
      Rec: 'a + Record<Cols = Cols> {
    type Iter = <Self as IntoIterator>::IntoIter;
    type Row = <Self as IntoIterator>::Item;
    fn execute(self)->Self::Iter { self.into_iter() }
}
`IntoIterator` for `&'a PeerJoin` implementation
impl<'a,L,R,K,RCols> IntoIterator for &'a PeerJoin<L,R> where
    L: Relation<'a> + SelfQuery<'a>,
    L::Item: Clone + 'a,
    R: Relation<'a>,
    K: Header + Eq + ProjectFrom<L::Cols> + Record + IntoFilter,
    <K as RecordImpl>::Cols: IntoFilter,
    for<'b> FilterRel<RelProxy<&'a R>, <K::Cols as IntoFilter>::Result>: SelfQuery<'b, Cols=R::Cols>,
    sexpr!{Intersect, {Phantom, @L::Cols}, @R::Cols}: Eval<Result=K>,
    PeerJoin<L,R>: RelationImpl,
    sexpr!{Remove, {Phantom, @K}, @R::Cols=r}:
        Calc<sexpr_quoted_types!{Remove, {Phantom, @K}, @R::Cols=r}, Result=RCols>,
    RCols: Header,
    (L::Item, RCols): Record,
    <PeerJoin<L,R> as RelationImpl>::Cols:
        ProjectFrom<<(L::Item, RCols) as RecordImpl>::Cols>
{
    type Item = Projection<(L::Item, RCols), <PeerJoin<L,R> as RelationImpl>::Cols>;
    type IntoIter = impl 'a + Iterator<Item = Self::Item>;
    fn into_iter(self)->Self::IntoIter {
        self.left.iter_all()
            .flat_map(move |l| {
                let key:K = (&l).project().into_cols();
                let tmp: Vec<_> = self.right.as_ref()
                    .where_eq(key).iter_all()
                    .map(|r|
                        calc!{Remove, {Phantom, @K}, @R::Cols=r.into_cols()}
                    )
                    .collect();
                tmp.into_iter().map(move |r| (l.clone(), r).project())
            })
    }
}
`Relation::as_ref` definition
    fn as_ref(&self)->RelProxy<&'_ Self> {
        RelProxy::new(self)
    }
`IntoIterator` for `&RelProxy<_>`
impl<'a, Ptr:Deref<Target=R>, R:Relation<'a>> IntoIterator for &'a RelProxy<Ptr> {
    type IntoIter = <R as SelfQuery<'a>>::Iter;
    type Item = R::Item;

    fn into_iter(self)->Self::IntoIter {
        let r:&'a R = &*self.0;
        r.iter_all()
    }
}
`IntoIterator` for `&OpaqueRel<_>`
impl<'a, R:Relation<'a>> IntoIterator for &'a OpaqueRel<R> {
    type IntoIter = <R as SelfQuery<'a>>::Iter;
    type Item = R::Item;

    fn into_iter(self)->Self::IntoIter {
        let r:&'a R = &self.0;
        r.iter_all()
    }
}

Apologies for the massive code dump, but I don't know where the problem lies.

Do you have a snippet with the full function that defines join?

Here's basically the entire file that defines PeerJoin; the error occurs in the test function at the end (minus imports and IntoIterator, which is listed above). I suspect the problem comes from one of the bounds in &PeerJoin<_>::IntoIterator, so I'm in the process of commenting them out one-by-one until the problem goes away.

pub struct PeerJoin<L, R> {
    left: L,
    right: R,
}

impl<L,R,K> RelationImpl for PeerJoin<L,R> where
    L: RelationImpl,
    R: RelationImpl,
    K: Header + Eq,
    sexpr!{Intersect, {Phantom, @L::Cols}, @R::Cols}: Eval<Result=K>,
    sexpr!{Union, @L::Cols, @R::Cols}: Eval,
    eval!{Union, @L::Cols, @R::Cols}: Header,
{
    type Cols = eval!{Union, @L::Cols, @R::Cols};
    type Planner = FallbackPlanner;
}

#[test]
fn test_peer_join() {
    use crate::relation::{OpaqueRel,Insert};
    use tylisp::sexpr_val;

    col!{A: usize}
    col!{B: usize}
    col!{C: usize}
    col!{D: usize}

    let mut left: OpaqueRel<Vec<sexpr!{A,B,C}>> = Default::default();
    let mut right: OpaqueRel<Vec<sexpr!{C,B,D}>> = Default::default();

    left.insert(sexpr_val!{A(1),B(2),C(3)}).unwrap();
    left.insert(sexpr_val!{A(2),B(2),C(7)}).unwrap();
    left.insert(sexpr_val!{A(3),B(5),C(7)}).unwrap();

    right.insert(sexpr_val!{D(1),B(2),C(3)}).unwrap();
    right.insert(sexpr_val!{D(2),B(2),C(7)}).unwrap();
    right.insert(sexpr_val!{D(3),B(5),C(7)}).unwrap();

    let join = PeerJoin { left: left.as_ref(), right: right.as_ref() };

    let _ = (&join).into_iter();
//    assert_eq!(join.iter_all().count(), 3);
}

As should probably not be a surprise, the HRTB appears to be the source of the problem. Now to figure out how to fix it.

for<'b> FilterRel<RelProxy<&'a R>, <K::Cols as IntoFilter>::Result>: SelfQuery<'b, Cols=R::Cols>

EDIT: Looks like I'm being caught by there being no syntax to bound arbitrarily-short lifetimes without also requiring arbitrarily-long ones. I need to call SelfQuery::iter_all on a local value of type FilterRel<_>. With the HRTB, the internal &R is forced to be valid for 'static; without it, I have to use the implementation lifetime 'a, which fails when the local variable goes out of scope.

Ah yes, that one can be very annoying

2 Likes

I've wanted syntax like for<'b where 'a:'b> a few times. I haven't ever gotten around to making a solid enough proposal for an IRLO post, though. I suspect the difficulty would be more in implementation than syntax, though.

1 Like

Semi-off: I'm not actually sure if that would in fact not require even-higher-rank types or something more powerful than what we have today w.r.t. lifetime subtyping (a System F<:-like calculus for lifetimes, maybe?). That for…where bound looks like the quantor is inside the subtype relation, and I don't remember my discrete maths 101 well enough to be able to tell if that's subject to skolemization.

IIRC, you may sometimes be able to circumvent this by removing trait-level impl level Self : 'a / T : 'a bound when possible, and when not, by moving the bound to the methods themselves:

- trait Foo<'lt> : 'lt {
+ trait Foo<'lt>       {
      fn method (…) -> _
+     where
+         Self : 'lt,
      { … }
  }

- impl<'lt, T : 'lt> Foo<'lt> for T
+ impl<'lt, T      > Foo<'lt> for T
  where
      T : …,
  {
      fn method (…) -> _
+     where
+         Self : 'lt,
      { … }
  }
2 Likes