chalk_engine/
stack.rs

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

chalk_engine/
stack.rs
