Repository: rust
Issue: ICE: deadlock due to query cycle
Labels: I-ICE,T-compiler,C-bug,A-parallel-queries,WG-compiler-parallel

<!--
Thank you for finding an Internal Compiler Error! 🧊  If possible, try to provide
a minimal verifiable example. You can read "Rust Bug Minimization Patterns" for
how to create smaller examples.
http://blog.pnkfx.org/blog/2019/11/18/rust-bug-minimization-patterns/
-->

### Code

```Rust
#![feature(generic_const_exprs)]

trait TensorDimension {
    const DIM: usize;
    const ISSCALAR: bool = Self::DIM == 0;
    fn is_scalar(&self) -> bool {
        Self::ISSCALAR
    }
}

trait TensorSize: TensorDimension {
    fn size(&self) -> [usize; Self::DIM];
    fn inbounds(&self, index: [usize; Self::DIM]) -> bool {
        index.iter().zip(self.size().iter()).all(|(i, s)| i < s)
    }
}

trait Broadcastable: TensorSize + Sized {
    type Element;
    fn bget(&self, index: [usize; Self::DIM]) -> Option<Self::Element>;
    fn lazy_updim<const NEWDIM: usize>(
        &self,
        size: [usize; NEWDIM],
    ) -> LazyUpdim<Self, { Self::DIM }, NEWDIM> {
        assert!(
            NEWDIM >= Self::DIM,
            "Updimmed tensor cannot have fewer indices than the initial one."
        ); // const generic bounds on nightly. ( )
        LazyUpdim {
            size,
            reference: &self,
        }
    }
    fn bmap<T, F: Fn(Self::Element) -> T>(&self, foo: F) -> BMap<T, Self, F, { Self::DIM }> {
        BMap {
            reference: self,
            closure: foo,
        }
    }
}

struct LazyUpdim<'a, T: Broadcastable, const OLDDIM: usize, const DIM: usize> {
    size: [usize; DIM],
    reference: &'a T,
}

impl<'a, T: Broadcastable, const DIM: usize> TensorDimension for LazyUpdim<'a, T, { T::DIM }, DIM> {
    const DIM: usize = DIM;
}
impl<'a, T: Broadcastable, const DIM: usize> TensorSize for LazyUpdim<'a, T, { T::DIM }, DIM> {
    fn size(&self) -> [usize; DIM] {
        self.size
    }
}
impl<'a, T: Broadcastable, const DIM: usize> Broadcastable for LazyUpdim<'a, T, { T::DIM }, DIM> {
    type Element = T::Element;
    fn bget(&self, index: [usize; DIM]) -> Option<Self::Element> {
        assert!(DIM >= T::DIM);
        if !self.inbounds(index) {
            return None;
        }
        let size = self.size();
        let newindex: [usize; T::DIM] = Default::default(); //array_init::array_init(|i| if size[i] > 1 {index[i]} else {0});
        self.reference.bget(newindex)
    }
}

struct BMap<'a, R, T: Broadcastable, F: Fn(T::Element) -> R, const DIM: usize> {
    reference: &'a T,
    closure: F,
}

impl<'a, R, T: Broadcastable, F: Fn(T::Element) -> R, const DIM: usize> TensorDimension
    for BMap<'a, R, T, F, DIM>
{
    const DIM: usize = DIM;
}
impl<'a, R, T: Broadcastable, F: Fn(T::Element) -> R, const DIM: usize> TensorSize
    for BMap<'a, R, T, F, DIM>
{
    fn size(&self) -> [usize; DIM] {
        self.reference.size()
    }
}
impl<'a, R, T: Broadcastable, F: Fn(T::Element) -> R, const DIM: usize> Broadcastable
    for BMap<'a, R, T, F, DIM>
{
    type Element = R;
    fn bget(&self, index: [usize; DIM]) -> Option<Self::Element> {
        self.reference.bget(index).map(ns_window)
    }
}

impl<T> TensorDimension for Vec<T> {
    const DIM: usize = 1;
}
impl<T> TensorSize for Vec<T> {
    fn size(&self) -> [usize; 1] {
        [self.len()]
    }
}
impl<T: Clone> Broadcastable for Vec<T> {
    type Element = T;
    fn bget(&self, index: [usize; 1]) -> Option<T> {
        self.get(index[0]).cloned()
    }
}

fn main() {
    let v = vec![1, 2, 3];
    let bv = v.lazy_updim([3, 4]);
    let bbv = bv.bmap(|x| x * x);

    println!(
        "The size of v is {:?}",
        bbv.bget([0, 2]).expect("Out of bounds.")
    );
}
```


### Meta
<!--
If you're using the stable version of the compiler, you should also check if the
bug also exists in the beta or nightly versions.
-->

`rustc --version --verbose`:
```
rustc 1.78.0-nightly (256b6fb19 2024-02-06)
binary: rustc
commit-hash: 256b6fb19a2c018eaad4806d2369d1f6a71fc6ec
commit-date: 2024-02-06
host: x86_64-unknown-linux-gnu
release: 1.78.0-nightly
LLVM version: 17.0.6
```

### Error output
`rustc -Zthreads=50 --crate-type lib file.rs`
```
error[E0425]: cannot find value `ns_window` in this scope
  --> /home/matthias/vcs/github/glacier2/fixed/icemaker_omni/CF35B2D494F3AAB8EA51CD645B1230546A5E59928436E15521DFFFB4D3856CCC.rs:90:40
   |
90 |         self.reference.bget(index).map(ns_window)
   |                                        ^^^^^^^^^ not found in this scope

warning: the feature `generic_const_exprs` is incomplete and may not be safe to use and/or cause compiler crashes
 --> /home/matthias/vcs/github/glacier2/fixed/icemaker_omni/CF35B2D494F3AAB8EA51CD645B1230546A5E59928436E15521DFFFB4D3856CCC.rs:1:12
  |
1 | #![feature(generic_const_exprs)]
  |            ^^^^^^^^^^^^^^^^^^^
  |
  = note: see issue #76560 <https://github.com/rust-lang/rust/issues/76560> for more information
  = note: `#[warn(incomplete_features)]` on by default

error[E0308]: method not compatible with trait
  --> /home/matthias/vcs/github/glacier2/fixed/icemaker_omni/CF35B2D494F3AAB8EA51CD645B1230546A5E59928436E15521DFFFB4D3856CCC.rs:81:5
   |
81 |     fn size(&self) -> [usize; DIM] {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected `Self::DIM`, found `DIM`
   |
   = note: expected constant `Self::DIM`
              found constant `DIM`

error[E0308]: method not compatible with trait
  --> /home/matthias/vcs/github/glacier2/fixed/icemaker_omni/CF35B2D494F3AAB8EA51CD645B1230546A5E59928436E15521DFFFB4D3856CCC.rs:89:5
   |
89 |     fn bget(&self, index: [usize; DIM]) -> Option<Self::Element> {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected `Self::DIM`, found `DIM`
   |
   = note: expected constant `Self::DIM`
              found constant `DIM`

error[E0391]: cycle detected when resolving instance `<LazyUpdim<'_, T, <T as TensorDimension>::DIM, DIM> as TensorDimension>::DIM`
  --> /home/matthias/vcs/github/glacier2/fixed/icemaker_omni/CF35B2D494F3AAB8EA51CD645B1230546A5E59928436E15521DFFFB4D3856CCC.rs:4:5
   |
4  |     const DIM: usize;
   |     ^^^^^^^^^^^^^^^^
   |
note: ...which requires computing candidate for `<LazyUpdim<'_, T, <T as TensorDimension>::DIM, DIM> as TensorDimension>`...
  --> /home/matthias/vcs/github/glacier2/fixed/icemaker_omni/CF35B2D494F3AAB8EA51CD645B1230546A5E59928436E15521DFFFB4D3856CCC.rs:3:1
   |
3  | trait TensorDimension {
   | ^^^^^^^^^^^^^^^^^^^^^
   = note: ...which again requires resolving instance `<LazyUpdim<'_, T, <T as TensorDimension>::DIM, DIM> as TensorDimension>::DIM`, completing the cycle
note: cycle used when checking that `<impl at /home/matthias/vcs/github/glacier2/fixed/icemaker_omni/CF35B2D494F3AAB8EA51CD645B1230546A5E59928436E15521DFFFB4D3856CCC.rs:55:1: 55:97>` is well-formed
  --> /home/matthias/vcs/github/glacier2/fixed/icemaker_omni/CF35B2D494F3AAB8EA51CD645B1230546A5E59928436E15521DFFFB4D3856CCC.rs:55:1
   |
55 | impl<'a, T: Broadcastable, const DIM: usize> Broadcastable for LazyUpdim<'a, T, { T::DIM }, DIM> {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   = note: see https://rustc-dev-guide.rust-lang.org/overview.html#queries and https://rustc-dev-guide.rust-lang.org/query.html for more information

error[E0391]: cycle detected when resolving instance `<LazyUpdim<'_, T, <T as TensorDimension>::DIM, DIM> as TensorDimension>::DIM`
 --> /home/matthias/vcs/github/glacier2/fixed/icemaker_omni/CF35B2D494F3AAB8EA51CD645B1230546A5E59928436E15521DFFFB4D3856CCC.rs:4:5
  |
4 |     const DIM: usize;
  |     ^^^^^^^^^^^^^^^^
  |
note: ...which requires computing candidate for `<LazyUpdim<'_, T, <T as TensorDimension>::DIM, DIM> as TensorDimension>`...
 --> /home/matthias/vcs/github/glacier2/fixed/icemaker_omni/CF35B2D494F3AAB8EA51CD645B1230546A5E59928436E15521DFFFB4D3856CCC.rs:3:1
  |
3 | trait TensorDimension {
  | ^^^^^^^^^^^^^^^^^^^^^
  = note: ...which again requires resolving instance `<LazyUpdim<'_, T, <T as TensorDimension>::DIM, DIM> as TensorDimension>::DIM`, completing the cycle
note: cycle used when computing candidate for `<LazyUpdim<'_, T, { T::DIM }, DIM> as TensorDimension>`
 --> /home/matthias/vcs/github/glacier2/fixed/icemaker_omni/CF35B2D494F3AAB8EA51CD645B1230546A5E59928436E15521DFFFB4D3856CCC.rs:3:1
  |
3 | trait TensorDimension {
  | ^^^^^^^^^^^^^^^^^^^^^
  = note: see https://rustc-dev-guide.rust-lang.org/overview.html#queries and https://rustc-dev-guide.rust-lang.org/query.html for more information
```

<!--
Include a backtrace in the code block by setting `RUST_BACKTRACE=1` in your
environment. E.g. `RUST_BACKTRACE=1 cargo build`.
-->
<details><summary><strong>Backtrace</strong></summary>
<p>

```
thread '<unnamed>' panicked at compiler/rustc_query_system/src/query/job.rs:545:13:
deadlock detected! current query map:
{
    QueryJobId(
        8765,
    ): QueryJobInfo {
        query: QueryStackFrame {
            description: "evaluating type-level constant",
            span: Some(
                Span {
                    lo: BytePos(
                        255,
                    ),
                    hi: BytePos(
                        264,
                    ),
                    ctxt: #0,
                },
            ),
            def_id: None,
            def_kind: None,
            ty_def_id: None,
            dep_kind: DepKind {
                variant: 126,
            },
            hash: 12867481825104948218,
        },
        job: QueryJob {
            id: QueryJobId(
                8765,
            ),
            span: Span {
                lo: BytePos(
                    1475,
                ),
                hi: BytePos(
                    1505,
                ),
                ctxt: #0,
            },
            parent: Some(
                QueryJobId(
                    8487,
                ),
            ),
            latch: None,
        },
    },
    QueryJobId(
        9034,
    ): QueryJobInfo {
        query: QueryStackFrame {
            description: "computing candidate for `<LazyUpdim<'_, T, <T as TensorDimension>::DIM, DIM> as TensorDimension>`",
            span: Some(
                Span {
                    lo: BytePos(
                        34,
                    ),
                    hi: BytePos(
                        55,
                    ),
                    ctxt: #0,
                },
            ),
            def_id: None,
            def_kind: None,
            ty_def_id: None,
            dep_kind: DepKind {
                variant: 159,
            },
            hash: 14524696915396724072,
        },
        job: QueryJob {
            id: QueryJobId(
                9034,
            ),
            span: Span {
                lo: BytePos(
                    0,
                ),
                hi: BytePos(
                    0,
                ),
                ctxt: #0,
            },
            parent: Some(
                QueryJobId(
                    9032,
                ),
            ),
            latch: None,
        },
    },
    QueryJobId(
        9031,
    ): QueryJobInfo {
        query: QueryStackFrame {
            description: "computing candidate for `<LazyUpdim<'_, T, { T::DIM }, DIM> as TensorDimension>`",
            span: Some(
                Span {
                    lo: BytePos(
                        34,
                    ),
                    hi: BytePos(
                        55,
                    ),
                    ctxt: #0,
                },
            ),
            def_id: None,
            def_kind: None,
            ty_def_id: None,
            dep_kind: DepKind {
                variant: 159,
            },
            hash: 7972346769609958538,
        },
        job: QueryJob {
            id: QueryJobId(
                9031,
            ),
            span: Span {
                lo: BytePos(
                    0,
                ),
                hi: BytePos(
                    0,
                ),
                ctxt: #0,
            },
            parent: Some(
                QueryJobId(
                    9030,
                ),
            ),
            latch: None,
        },
    },
    QueryJobId(
        8292,
    ): QueryJobInfo {
        query: QueryStackFrame {
            description: "checking that types are well-formed in top-level module",
            span: Some(
                Span {
                    lo: BytePos(
                        0,
                    ),
                    hi: BytePos(
                        3306,
                    ),
                    ctxt: #0,
                },
            ),
            def_id: Some(
                DefId(0:0),
            ),
            def_kind: Some(
                Mod,
            ),
            ty_def_id: None,
            dep_kind: DepKind {
                variant: 110,
            },
            hash: 5322523677691242860,
        },
        job: QueryJob {
            id: QueryJobId(
                8292,
            ),
            span: Span {
                lo: BytePos(
                    0,
                ),
                hi: BytePos(
                    0,
                ),
                ctxt: #0,
            },
            parent: Some(
                QueryJobId(
                    7297,
                ),
            ),
            latch: None,
        },
    },
    QueryJobId(
        7297,
    ): QueryJobInfo {
        query: QueryStackFrame {
            description: "running analysis passes on this crate",
            span: Some(
                Span {
                    lo: BytePos(
                        0,
                    ),
                    hi: BytePos(
                        0,
                    ),
                    ctxt: #0,
                },
            ),
            def_id: None,
            def_kind: None,
            ty_def_id: None,
            dep_kind: DepKind {
                variant: 25,
            },
            hash: 5462938028500440564,
        },
        job: QueryJob {
            id: QueryJobId(
                7297,
            ),
            span: Span {
                lo: BytePos(
                    0,
                ),
                hi: BytePos(
                    0,
                ),
                ctxt: #0,
            },
            parent: None,
            latch: None,
        },
    },
    QueryJobId(
        8487,
    ): QueryJobInfo {
        query: QueryStackFrame {
            description: "checking that `<impl at /home/matthias/vcs/github/glacier2/fixed/icemaker_omni/CF35B2D494F3AAB8EA51CD645B1230546A5E59928436E15521DFFFB4D3856CCC.rs:50:1: 50:94>` is well-formed",
            span: Some(
                Span {
                    lo: BytePos(
                        1375,
                    ),
                    hi: BytePos(
                        1468,
                    ),
                    ctxt: #0,
                },
            ),
            def_id: Some(
                DefId(0:39),
            ),
            def_kind: Some(
                Impl {
                    of_trait: true,
                },
            ),
            ty_def_id: None,
            dep_kind: DepKind {
                variant: 195,
            },
            hash: 11679696925837849750,
        },
        job: QueryJob {
            id: QueryJobId(
                8487,
            ),
            span: Span {
                lo: BytePos(
                    0,
                ),
                hi: BytePos(
                    0,
                ),
                ctxt: #0,
            },
            parent: Some(
                QueryJobId(
                    8292,
                ),
            ),
            latch: None,
        },
    },
    QueryJobId(
        9032,
    ): QueryJobInfo {
        query: QueryStackFrame {
            description: "resolving instance `<LazyUpdim<'_, T, <T as TensorDimension>::DIM, DIM> as TensorDimension>::DIM`",
            span: Some(
                Span {
                    lo: BytePos(
                        62,
                    ),
                    hi: BytePos(
                        78,
                    ),
                    ctxt: #0,
                },
            ),
            def_id: None,
            def_kind: None,
            ty_def_id: None,
            dep_kind: DepKind {
                variant: 278,
            },
            hash: 10795639758650191788,
        },
        job: QueryJob {
            id: QueryJobId(
                9032,
            ),
            span: Span {
                lo: BytePos(
                    0,
                ),
                hi: BytePos(
                    0,
                ),
                ctxt: #0,
            },
            parent: Some(
                QueryJobId(
                    9031,
                ),
            ),
            latch: Some(
                QueryLatch {
                    info: Mutex {
                        data: QueryLatchInfo {
                            complete: true,
                            waiters: [],
                        },
                    },
                },
            ),
        },
    },
    QueryJobId(
        8767,
    ): QueryJobInfo {
        query: QueryStackFrame {
            description: "const-evaluating + checking `TensorSize::size::{constant#0}`",
            span: Some(
                Span {
                    lo: BytePos(
                        255,
                    ),
                    hi: BytePos(
                        264,
                    ),
                    ctxt: #0,
                },
            ),
            def_id: None,
            def_kind: None,
            ty_def_id: None,
            dep_kind: DepKind {
                variant: 124,
            },
            hash: 16033137702957887872,
        },
        job: QueryJob {
            id: QueryJobId(
                8767,
            ),
            span: Span {
                lo: BytePos(
                    0,
                ),
                hi: BytePos(
                    0,
                ),
                ctxt: #0,
            },
            parent: Some(
                QueryJobId(
                    8765,
                ),
            ),
            latch: None,
        },
    },
    QueryJobId(
        9030,
    ): QueryJobInfo {
        query: QueryStackFrame {
            description: "resolving instance `<LazyUpdim<'_, T, { T::DIM }, DIM> as TensorDimension>::DIM`",
            span: Some(
                Span {
                    lo: BytePos(
                        62,
                    ),
                    hi: BytePos(
                        78,
^[[A                    ),
                    ctxt: #0,
                },
            ),
            def_id: None,
            def_kind: None,
            ty_def_id: None,
            dep_kind: DepKind {
                variant: 278,
            },
            hash: 16370839285763878492,
        },
        job: QueryJob {
            id: QueryJobId(
                9030,
            ),
            span: Span {
                lo: BytePos(
                    0,
                ),
                hi: BytePos(
                    0,
                ),
                ctxt: #0,
            },
            parent: Some(
                QueryJobId(
                    8767,
                ),
            ),
            latch: None,
        },
    },
}
stack backtrace:
error: aborting due to 5 previous errors; 1 warning emitted

Some errors have detailed explanations: E0308, E0391, E0425.
For more information about an error, try `rustc --explain E0308`.
```

</p>
</details>