rustc_type_ir/search_graph/
stack.rs

1use std::ops::Index;
2
3use derive_where::derive_where;
4use rustc_index::IndexVec;
5
6use crate::search_graph::{
7    AvailableDepth, CandidateHeadUsages, Cx, CycleHeads, HeadUsages, NestedGoals, PathKind,
8};
9
10impl ::std::fmt::Debug for StackDepth {
    fn fmt(&self, fmt: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result {
        fmt.write_fmt(format_args!("{0}", self.as_u32()))
    }
}rustc_index::newtype_index! {
11    #[orderable]
12    #[gate_rustc_only]
13    pub(super) struct StackDepth {}
14}
15
16/// Stack entries of the evaluation stack. Its fields tend to be lazily updated
17/// when popping a child goal or completely immutable.
18#[automatically_derived]
impl<X: Cx> ::core::fmt::Debug for StackEntry<X> where X: Cx {
    fn fmt(&self, __f: &mut ::core::fmt::Formatter<'_>)
        -> ::core::fmt::Result {
        match self {
            StackEntry {
                input: ref __field_input,
                step_kind_from_parent: ref __field_step_kind_from_parent,
                available_depth: ref __field_available_depth,
                min_reached_available_depth: ref __field_min_reached_available_depth,
                provisional_result: ref __field_provisional_result,
                heads: ref __field_heads,
                encountered_overflow: ref __field_encountered_overflow,
                usages: ref __field_usages,
                candidate_usages: ref __field_candidate_usages,
                nested_goals: ref __field_nested_goals } => {
                let mut __builder =
                    ::core::fmt::Formatter::debug_struct(__f, "StackEntry");
                ::core::fmt::DebugStruct::field(&mut __builder, "input",
                    __field_input);
                ::core::fmt::DebugStruct::field(&mut __builder,
                    "step_kind_from_parent", __field_step_kind_from_parent);
                ::core::fmt::DebugStruct::field(&mut __builder,
                    "available_depth", __field_available_depth);
                ::core::fmt::DebugStruct::field(&mut __builder,
                    "min_reached_available_depth",
                    __field_min_reached_available_depth);
                ::core::fmt::DebugStruct::field(&mut __builder,
                    "provisional_result", __field_provisional_result);
                ::core::fmt::DebugStruct::field(&mut __builder, "heads",
                    __field_heads);
                ::core::fmt::DebugStruct::field(&mut __builder,
                    "encountered_overflow", __field_encountered_overflow);
                ::core::fmt::DebugStruct::field(&mut __builder, "usages",
                    __field_usages);
                ::core::fmt::DebugStruct::field(&mut __builder,
                    "candidate_usages", __field_candidate_usages);
                ::core::fmt::DebugStruct::field(&mut __builder,
                    "nested_goals", __field_nested_goals);
                ::core::fmt::DebugStruct::finish(&mut __builder)
            }
        }
    }
}#[derive_where(Debug; X: Cx)]
19pub(super) struct StackEntry<X: Cx> {
20    pub input: X::Input,
21
22    /// Whether proving this goal is a coinductive step.
23    ///
24    /// This is used when encountering a trait solver cycle to
25    /// decide whether the initial provisional result of the cycle.
26    pub step_kind_from_parent: PathKind,
27
28    /// The available depth of a given goal, immutable.
29    pub available_depth: AvailableDepth,
30
31    /// The minimum available depth encountered while evaluating this goal's nested goals.
32    /// If there's no nested goal, this is equal to the `available_depth`.
33    pub min_reached_available_depth: AvailableDepth,
34
35    /// Starts out as `None` and gets set when rerunning this
36    /// goal in case we encounter a cycle.
37    pub provisional_result: Option<X::Result>,
38
39    /// All cycle heads this goal depends on. Lazily updated and only
40    /// up-to date for the top of the stack.
41    pub heads: CycleHeads,
42
43    /// Whether evaluating this goal encountered overflow. Lazily updated.
44    pub encountered_overflow: bool,
45
46    /// Whether and how this goal has been used as a cycle head. Lazily updated.
47    pub usages: Option<HeadUsages>,
48
49    /// We want to be able to ignore head usages if they happen inside of candidates
50    /// which don't impact the result of a goal. This enables us to avoid rerunning goals
51    /// and is also used when rebasing provisional cache entries.
52    ///
53    /// To implement this, we track all usages while evaluating a candidate. If this candidate
54    /// then ends up ignored, we manually remove its usages from `usages` and `heads`.
55    pub candidate_usages: Option<CandidateHeadUsages>,
56
57    /// The nested goals of this goal, see the doc comment of the type.
58    pub nested_goals: NestedGoals<X>,
59}
60
61impl<X: Cx> StackEntry<X> {
62    pub(super) fn required_depth(&self) -> usize {
63        self.available_depth.0 - self.min_reached_available_depth.0
64    }
65}
66
67/// The stack of goals currently being computed.
68///
69/// An element is *deeper* in the stack if its index is *lower*.
70///
71/// Only the last entry of the stack is mutable. All other entries get
72/// lazily updated in `update_parent_goal`.
73#[automatically_derived]
impl<X: Cx> ::core::default::Default for Stack<X> where X: Cx {
    fn default() -> Self {
        Stack { entries: ::core::default::Default::default() }
    }
}#[derive_where(Default; X: Cx)]
74pub(super) struct Stack<X: Cx> {
75    entries: IndexVec<StackDepth, StackEntry<X>>,
76}
77
78impl<X: Cx> Stack<X> {
79    pub(super) fn is_empty(&self) -> bool {
80        self.entries.is_empty()
81    }
82
83    pub(super) fn len(&self) -> usize {
84        self.entries.len()
85    }
86
87    pub(super) fn last(&self) -> Option<&StackEntry<X>> {
88        self.entries.raw.last()
89    }
90
91    pub(super) fn last_mut(&mut self) -> Option<&mut StackEntry<X>> {
92        self.entries.raw.last_mut()
93    }
94
95    pub(super) fn last_mut_with_index(&mut self) -> Option<(StackDepth, &mut StackEntry<X>)> {
96        self.entries.last_index().map(|idx| (idx, &mut self.entries[idx]))
97    }
98
99    pub(super) fn next_index(&self) -> StackDepth {
100        self.entries.next_index()
101    }
102
103    pub(super) fn push(&mut self, entry: StackEntry<X>) -> StackDepth {
104        if truecfg!(debug_assertions) && self.entries.iter().any(|e| e.input == entry.input) {
105            {
    ::core::panicking::panic_fmt(format_args!("pushing duplicate entry on stack: {1:?} {0:?}",
            self.entries, entry));
};panic!("pushing duplicate entry on stack: {entry:?} {:?}", self.entries);
106        }
107        self.entries.push(entry)
108    }
109
110    pub(super) fn pop(&mut self) -> StackEntry<X> {
111        self.entries.pop().unwrap()
112    }
113
114    pub(super) fn cycle_step_kinds(&self, head: StackDepth) -> impl Iterator<Item = PathKind> {
115        self.entries.raw[head.index() + 1..].iter().map(|entry| entry.step_kind_from_parent)
116    }
117
118    pub(super) fn iter(&self) -> impl Iterator<Item = &StackEntry<X>> {
119        self.entries.iter()
120    }
121
122    pub(super) fn find(&self, input: X::Input) -> Option<StackDepth> {
123        self.entries.iter_enumerated().find(|(_, e)| e.input == input).map(|(idx, _)| idx)
124    }
125}
126
127impl<X: Cx> Index<StackDepth> for Stack<X> {
128    type Output = StackEntry<X>;
129    fn index(&self, index: StackDepth) -> &StackEntry<X> {
130        &self.entries[index]
131    }
132}
rustc_type_ir/search_graph/stack.rs

rustc_type_ir/search_graph/
stack.rs
