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 }