rustc_type_ir/search_graph/
stack.rs

1use std::ops::{Index, IndexMut};
2
3use derive_where::derive_where;
4use rustc_index::IndexVec;
5
6use super::{AvailableDepth, Cx, CycleHeads, NestedGoals, PathKind, UsageKind};
7
8rustc_index::newtype_index! {
9    #[orderable]
10    #[gate_rustc_only]
11    pub(super) struct StackDepth {}
12}
13
14/// Stack entries of the evaluation stack. Its fields tend to be lazily
15/// when popping a child goal or completely immutable.
16#[derive_where(Debug; X: Cx)]
17pub(super) struct StackEntry<X: Cx> {
18    pub input: X::Input,
19
20    /// Whether proving this goal is a coinductive step.
21    ///
22    /// This is used when encountering a trait solver cycle to
23    /// decide whether the initial provisional result of the cycle.
24    pub step_kind_from_parent: PathKind,
25
26    /// The available depth of a given goal, immutable.
27    pub available_depth: AvailableDepth,
28
29    /// Starts out as `None` and gets set when rerunning this
30    /// goal in case we encounter a cycle.
31    pub provisional_result: Option<X::Result>,
32
33    /// The maximum depth required while evaluating this goal.
34    pub required_depth: usize,
35
36    /// All cycle heads this goal depends on. Lazily updated and only
37    /// up-to date for the top of the stack.
38    pub heads: CycleHeads,
39
40    /// Whether evaluating this goal encountered overflow. Lazily updated.
41    pub encountered_overflow: bool,
42
43    /// Whether this goal has been used as the root of a cycle. This gets
44    /// eagerly updated when encountering a cycle.
45    pub has_been_used: Option<UsageKind>,
46
47    /// The nested goals of this goal, see the doc comment of the type.
48    pub nested_goals: NestedGoals<X>,
49}
50
51#[derive_where(Default; X: Cx)]
52pub(super) struct Stack<X: Cx> {
53    entries: IndexVec<StackDepth, StackEntry<X>>,
54}
55
56impl<X: Cx> Stack<X> {
57    pub(super) fn is_empty(&self) -> bool {
58        self.entries.is_empty()
59    }
60
61    pub(super) fn len(&self) -> usize {
62        self.entries.len()
63    }
64
65    pub(super) fn last_index(&self) -> Option<StackDepth> {
66        self.entries.last_index()
67    }
68
69    pub(super) fn last(&self) -> Option<&StackEntry<X>> {
70        self.entries.raw.last()
71    }
72
73    pub(super) fn last_mut(&mut self) -> Option<&mut StackEntry<X>> {
74        self.entries.raw.last_mut()
75    }
76
77    pub(super) fn next_index(&self) -> StackDepth {
78        self.entries.next_index()
79    }
80
81    pub(super) fn push(&mut self, entry: StackEntry<X>) -> StackDepth {
82        self.entries.push(entry)
83    }
84
85    pub(super) fn pop(&mut self) -> StackEntry<X> {
86        self.entries.pop().unwrap()
87    }
88
89    pub(super) fn cycle_step_kinds(&self, head: StackDepth) -> impl Iterator<Item = PathKind> {
90        self.entries.raw[head.index() + 1..].iter().map(|entry| entry.step_kind_from_parent)
91    }
92
93    pub(super) fn iter(&self) -> impl Iterator<Item = &StackEntry<X>> {
94        self.entries.iter()
95    }
96
97    pub(super) fn find(&self, input: X::Input) -> Option<StackDepth> {
98        self.entries.iter_enumerated().find(|(_, e)| e.input == input).map(|(idx, _)| idx)
99    }
100}
101
102impl<X: Cx> Index<StackDepth> for Stack<X> {
103    type Output = StackEntry<X>;
104    fn index(&self, index: StackDepth) -> &StackEntry<X> {
105        &self.entries[index]
106    }
107}
108
109impl<X: Cx> IndexMut<StackDepth> for Stack<X> {
110    fn index_mut(&mut self, index: StackDepth) -> &mut Self::Output {
111        &mut self.entries[index]
112    }
113}
rustc_type_ir/search_graph/stack.rs

rustc_type_ir/search_graph/
stack.rs
