Rust: Borrowck deduces empty lifetime

[dingxiangfei2009]

I tried this code:

use std::ops::{DivAssign, SubAssign};

use ndarray::{s, Array2, ArrayView1, Axis, Zip};
use num::{Zero, One};
use rayon::prelude::*;

pub fn gaussian_elimination<T>(mut a: Array2<T>) -> Array2<T>
where
    T: One + Zero + Clone + Send + Sync + DivAssign + SubAssign,
{
    let (n, m) = a.dim();
    assert!(n > 0);
    let mut pivots = vec![];
    let mut pivot = 0;
    for i in 0..n {
        if a[[i, pivot]].is_zero() {
            if let Some((new_pivot, row)) = (pivot..m)
                .into_par_iter()
                .flat_map(|pivot| {
                    let a: ArrayView1<_> = a.slice(s![i.., pivot]);
                    a.axis_iter(Axis(0))
                        .into_par_iter()
                        .enumerate()
                        .flat_map(|(j, x)| {
                            if x.into_scalar().is_zero() {
                                None
                            } else {
                                Some(j)
                            }
                        })
                        .find_any(|_| true)
                        .map(|row| (pivot, row))
                })
                .find_first(|_| true)
            {
                pivot = new_pivot;
                if row > 0 {
                    let mut a = a.slice_mut(s![i..; row, ..]);
                    let mut it = a.axis_iter_mut(Axis(0));
                    let this_row = it.next().expect("this row exists");
                    let that_row = it.next().expect("that row exists");
                    Zip::from(this_row).and(that_row).par_apply(std::mem::swap);
                }
            } else {
                break;
            }
        }
        pivots.push((i, pivot));
        let (mut this_equation, mut rest_equations) = a.slice_mut(s![i.., ..]).split_at(Axis(0), 1);
        let mut this_equation = this_equation.index_axis_mut(Axis(0), 0);
        let scale = this_equation[pivot].clone();
        assert!(!scale.is_zero());
        this_equation.iter_mut().for_each(|a| {
            *a /= scale.clone();
        });

        rest_equations
            .axis_iter_mut(Axis(0))
            .into_par_iter()
            .for_each(|mut eqn| {
                let scale = eqn[pivot].clone();
                if !scale.is_zero() {
                    eqn.iter_mut()
                        .zip(this_equation.iter())
                        .for_each(|(e, e_)| *e -= e_.clone() * scale.clone());
                }
            });
        pivot += 1;
        if pivot >= m {
            break;
        }
    }

    // a is in row echelon form now
    if pivots.len() > 1 {
        for (i, pivot) in pivots[1..].iter().rev() {
            let (mut rest_equations, this_equation) =
                a.slice_mut(s![..=*i, ..]).split_at(Axis(0), *i);
            let this_equation = this_equation.index_axis(Axis(0), 0);
            rest_equations.axis_iter_mut(Axis(0)).for_each(|eqn| {
                if eqn[*pivot].is_zero() {
                    return;
                }
                let scale = eqn[*pivot].clone();
                Zip::from(eqn)
                    .and(this_equation)
                    .par_apply(|e, e_| *e -= e_.clone() * scale.clone());
            });
        }
    }

    a
}

I expected to see this happen:
On Rust 1.44.0, this compiles.

Instead, this happened:

error[E0311]: the parameter type `T` may not live long enough
  --> src/lib.rs:85:17
   |
85 | /                 Zip::from(eqn)
86 | |                     .and(this_equation)
   | |_______________________________________^
   |
   = note: the parameter type `T` must be valid for the empty lifetime...
   = note: ...so that the reference type `&T` does not outlive the data it points at

error: aborting due to previous error

Meta

rustc --version --verbose:

rustc 1.46.0-nightly (346aec9b0 2020-07-11)
binary: rustc
commit-hash: 346aec9b02f3c74f3fce97fd6bda24709d220e49
commit-date: 2020-07-11
host: x86_64-unknown-linux-gnu
release: 1.46.0-nightly
LLVM version: 10.0

[dingxiangfei2009]

For reproduction, the following Cargo.toml is used.

[package]
name = "testrust"
version = "0.1.0"
edition = "2018"

[dependencies]
rayon = "1.3.0"
num = "0.2.0"

[dependencies.ndarray]
version = "0.13.0"
features = ["rayon"]

[dingxiangfei2009]

This is a regression from stable to nightly.

[LeSeulArtichaut]

Let’s bisect this and try to find an MCVE.
@rustbot ping cleanup

[rustbot]

Hey Cleanup Crew ICE-breakers! This bug has been identified as a good
"Cleanup ICE-breaking candidate". In case it's useful, here are some
[instructions] for tackling these sorts of bugs. Maybe take a look?
Thanks! <3

cc @AminArria @camelid @chrissimpkins @contrun @DutchGhost @elshize @ethanboxx @h-michael @HallerPatrick @hdhoang @hellow554 @imtsuki @kanru @KarlK90 @LeSeulArtichaut @MAdrianMattocks @matheus-consoli @mental32 @nmccarty @Noah-Kennedy @pard68 @PeytonT @pierreN @Redblueflame @RobbieClarken @RobertoSnap @robjtede @SarthakSingh31 @senden9 @shekohex @sinato @spastorino @turboladen @woshilapin @yerke

[SNCPlay42]

The code succeeds to compile on 1.44.1 and fails on 1.45, so this is actually a stable-to-stable regression.

[spastorino]

Assigning P-critical as discussed as part of the Prioritization Working Group procedure and removing I-prioritize.

[SNCPlay42]

So far I've reduced it to this, which depends only on ndarray (without the rayon feature):

use ndarray::{s, Array2, Axis, Zip};

pub fn gaussian_elimination<T>(mut a: Array2<T>)
{
    let (mut rest_equations, this_equation) =
        a.slice_mut(s![..=0, ..]).split_at(Axis(0), 0);
    let this_equation = this_equation.index_axis(Axis(0), 0);
    rest_equations.axis_iter_mut(Axis(0)).for_each(|_eqn| {
        Zip::from(this_equation);
    });
}

[SNCPlay42]

cargo bisect-rustc:

searched nightlies: from nightly-2020-04-20 to nightly-2020-06-02
regressed nightly: nightly-2020-05-25
searched commits: from https://github.com/rust-lang/rust/commit/8970e8bcf6153d1ead2283f1a0ed7b192230eca6 to https://github.com/rust-lang/rust/commit/46e85b4328fe18492894093c1092dfe509df4370
regressed commit: https://github.com/rust-lang/rust/commit/52b605c8cb2f730e607de0777a694cd1b9bb3e15

bisected with cargo-bisect-rustc v0.5.2

Host triple: x86_64-unknown-linux-gnu
Reproduce with:

cargo bisect-rustc --start 2020-04-20 --end 2020-06-02 

regressed in #72362

[dingxiangfei2009]

@SNCPlay42 The reproduction does not produce error in rustc 1.46.0-nightly (346aec9b0 2020-07-11).
However, I find this throws error on this nightly, as well as on 1.45.0.

use ndarray::{s, Array2, Axis, Zip};

pub fn gaussian_elimination<T>(a: Array2<T>)
{
    (0..1).filter(|_| true);

    let (rest_equations, this_equation) =
        a.slice(s![.., ..]).split_at(Axis(0), 0);
    let this_equation = this_equation.index_axis(Axis(0), 0);
    rest_equations.axis_iter(Axis(0)).for_each(|_| {
        Zip::from(this_equation);
    });
}

Here is an even shorter one:

use ndarray::{Array2, Axis, Zip};

fn x<T>(a: Array2<T>) {
    (0..1).filter(|_| true);
    let y = a.index_axis(Axis(0), 0);
    a.axis_iter(Axis(0)).for_each(|_| {
        Zip::from(y);
    });
}

The line (0..1).filter(|_| true); seems critical. Without this, there will be no reproduction with both snippets.

This is also reproducible on the nightly rustc 1.46.0-nightly (2020-07-16 5c9e5df3a097e094641f).

[jonas-schievink]

cc @matthewjasper

[SNCPlay42]

The PR that made my reduced code (without (0..1).filter(|_| true);) start successfully compiling again is #73643, in case it helps show what's going on.

Full bisect-rustc

searched nightlies: from nightly-2020-05-25 to nightly-2020-07-17
regressed nightly: nightly-2020-06-24
searched commits: from https://github.com/rust-lang/rust/commit/6bb3dbfc6c6d8992d08431f320ba296a0c2f7498 to https://github.com/rust-lang/rust/commit/ff5b446d2fdbd898bc97a751f2f72858de185cf1
regressed commit: https://github.com/rust-lang/rust/commit/1557fb031b272b4c5bfcc7de5df7eddc7b36a584

bisected with cargo-bisect-rustc v0.5.2

Host triple: x86_64-unknown-linux-gnu
Reproduce with:

cargo bisect-rustc --start 2020-05-25 --regress non-error 

[SNCPlay42]

Single-crate repro:

use std::marker::PhantomData;
use std::ptr::NonNull;
pub unsafe trait RawData {
    type Elem;
}
unsafe impl<A> RawData for OwnedRepr<A> {
    type Elem = A;
}
unsafe impl<'a, A> RawData for ViewRepr<&'a A> {
    type Elem = A;
}
pub struct OwnedRepr<A> {
    ptr: PhantomData<A>,
}
// these Copy impls are not necessary for the repro, but allow the code to compile without error
// on 1.44.1
#[derive(Copy, Clone)]
pub struct ViewRepr<A> {
    life: PhantomData<A>,
}
#[derive(Copy, Clone)]
pub struct ArrayBase<S>
where
    S: RawData,
{
    ptr: NonNull<S::Elem>,
}
pub type Array<A> = ArrayBase<OwnedRepr<A>>;
pub type ArrayView<'a, A> = ArrayBase<ViewRepr<&'a A>>;
impl<A, S> ArrayBase<S>
where
    S: RawData<Elem = A>,
{
    pub fn index_axis(&self) -> ArrayView<'_, A> {
        unimplemented!()
    }
    pub fn axis_iter<'a>(&'a self) -> std::iter::Empty<&'a A> {
        unimplemented!()
    }
}
pub fn x<T: Copy>(a: Array<T>) {
    // drop just avoids a must_use warning
    drop((0..1).filter(|_| true));
    let y = a.index_axis();
    a.axis_iter().for_each(|_| {
        drop(y);
    });
}

[dingxiangfei2009]

I can volunteer myself for looking into the issue. I have a question about the region inference. Is there a way to visualize, or trace the region inference? Guidance and mentoring instructions are _very_ welcome. :smile: