]> git.proxmox.com Git - rustc.git/blob - vendor/chalk-engine/src/stack.rs
New upstream version 1.48.0~beta.8+dfsg1
[rustc.git] / vendor / chalk-engine / src / stack.rs
1 use crate::context::Context;
2 use crate::index_struct;
3 use crate::strand::Strand;
4 use crate::tables::Tables;
5 use crate::{Minimums, TableIndex, TimeStamp};
6 use std::fmt;
7 use std::ops::{Index, IndexMut, Range};
8
9 use chalk_ir::interner::Interner;
10
11 /// See `Forest`.
12 #[derive(Debug)]
13 pub(crate) struct Stack<I: Interner, C: Context<I>> {
14 /// Stack: as described above, stores the in-progress goals.
15 stack: Vec<StackEntry<I, C>>,
16 }
17
18 impl<I: Interner, C: Context<I>> Stack<I, C> {
19 // This isn't actually used, but it can be helpful when debugging stack issues
20 #[allow(dead_code)]
21 pub(crate) fn debug_with<'a>(&'a self, tables: &'a Tables<I>) -> StackDebug<'_, I, C> {
22 StackDebug {
23 stack: self,
24 tables,
25 }
26 }
27 }
28
29 pub(crate) struct StackDebug<'a, I: Interner, C: Context<I>> {
30 stack: &'a Stack<I, C>,
31 tables: &'a Tables<I>,
32 }
33
34 impl<I: Interner, C: Context<I>> fmt::Debug for StackDebug<'_, I, C> {
35 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
36 writeln!(f, "---- Stack ----")?;
37 for entry in self.stack.stack.iter() {
38 writeln!(f, " --- StackEntry ---")?;
39 writeln!(
40 f,
41 " Table {:?} with goal {:?}",
42 entry.table, self.tables[entry.table].table_goal
43 )?;
44 writeln!(f, " Active strand: {:#?}", entry.active_strand)?;
45 writeln!(
46 f,
47 " Additional strands: {:#?}",
48 self.tables[entry.table].strands().collect::<Vec<_>>()
49 )?;
50 }
51 write!(f, "---- End Stack ----")?;
52 Ok(())
53 }
54 }
55
56 impl<I: Interner, C: Context<I>> Default for Stack<I, C> {
57 fn default() -> Self {
58 Stack { stack: vec![] }
59 }
60 }
61
62 index_struct! {
63 /// The StackIndex identifies the position of a table's goal in the
64 /// stack of goals that are actively being processed. Note that once a
65 /// table is completely evaluated, it may be popped from the stack,
66 /// and hence no longer have a stack index.
67 pub(crate) struct StackIndex {
68 value: usize,
69 }
70 }
71
72 #[derive(Debug)]
73 pub(crate) struct StackEntry<I: Interner, C: Context<I>> {
74 /// The goal G from the stack entry `A :- G` represented here.
75 pub(super) table: TableIndex,
76
77 /// The clock TimeStamp of this stack entry.
78 pub(super) clock: TimeStamp,
79
80 pub(super) cyclic_minimums: Minimums,
81
82 // FIXME: should store this as an index.
83 // This would mean that if we unwind,
84 // we don't need to worry about losing a strand
85 pub(super) active_strand: Option<Strand<I, C>>,
86 }
87
88 impl<I: Interner, C: Context<I>> Stack<I, C> {
89 pub(super) fn is_empty(&self) -> bool {
90 self.stack.is_empty()
91 }
92
93 /// Searches the stack to see if `table` is active. If so, returns
94 /// its stack index.
95 pub(super) fn is_active(&self, table: TableIndex) -> Option<StackIndex> {
96 self.stack
97 .iter()
98 .enumerate()
99 .filter_map(|(index, stack_entry)| {
100 if stack_entry.table == table {
101 Some(StackIndex::from(index))
102 } else {
103 None
104 }
105 })
106 .next()
107 }
108
109 pub(super) fn top_of_stack_from(&self, depth: StackIndex) -> Range<StackIndex> {
110 depth..StackIndex::from(self.stack.len())
111 }
112
113 pub(super) fn push(
114 &mut self,
115 table: TableIndex,
116 cyclic_minimums: Minimums,
117 clock: TimeStamp,
118 ) -> StackIndex {
119 let old_len = self.stack.len();
120 self.stack.push(StackEntry {
121 table,
122 clock,
123 cyclic_minimums,
124 active_strand: None,
125 });
126 StackIndex::from(old_len)
127 }
128
129 /// Pops the top-most entry from the stack:
130 /// * If the stack is now empty, returns false.
131 /// * Otherwise, returns true.
132 fn pop_and_adjust_depth(&mut self) -> bool {
133 self.stack.pop();
134 !self.stack.is_empty()
135 }
136
137 /// Pops the top-most entry from the stack, which should have the depth `*depth`:
138 /// * If the stack is now empty, returns None.
139 /// * Otherwise, `take`s the active strand from the new top and returns it.
140 pub(super) fn pop_and_take_caller_strand(&mut self) -> Option<Strand<I, C>> {
141 if self.pop_and_adjust_depth() {
142 Some(self.top().active_strand.take().unwrap())
143 } else {
144 None
145 }
146 }
147
148 /// Pops the top-most entry from the stack, which should have the depth `*depth`:
149 /// * If the stack is now empty, returns None.
150 /// * Otherwise, borrows the active strand (mutably) from the new top and returns it.
151 pub(super) fn pop_and_borrow_caller_strand(&mut self) -> Option<&mut Strand<I, C>> {
152 if self.pop_and_adjust_depth() {
153 Some(self.top().active_strand.as_mut().unwrap())
154 } else {
155 None
156 }
157 }
158
159 pub(super) fn top(&mut self) -> &mut StackEntry<I, C> {
160 self.stack.last_mut().unwrap()
161 }
162 }
163
164 impl<I: Interner, C: Context<I>> Index<StackIndex> for Stack<I, C> {
165 type Output = StackEntry<I, C>;
166
167 fn index(&self, index: StackIndex) -> &StackEntry<I, C> {
168 &self.stack[index.value]
169 }
170 }
171
172 impl<I: Interner, C: Context<I>> IndexMut<StackIndex> for Stack<I, C> {
173 fn index_mut(&mut self, index: StackIndex) -> &mut StackEntry<I, C> {
174 &mut self.stack[index.value]
175 }
176 }