vendor/chalk-engine-0.14.0/src/stack.rs

   1 use crate::context::Context;
   2 use crate::index_struct;
   3 use crate::strand::Strand;
   4 use crate::{Minimums, TableIndex, TimeStamp};
   5 use std::ops::{Index, IndexMut, Range};
   6
   7 use chalk_ir::interner::Interner;
   8
   9 /// See `Forest`.
  10 #[derive(Debug)]
  11 pub(crate) struct Stack<I: Interner, C: Context<I>> {
  12     /// Stack: as described above, stores the in-progress goals.
  13     stack: Vec<StackEntry<I, C>>,
  14 }
  15
  16 impl<I: Interner, C: Context<I>> Default for Stack<I, C> {
  17     fn default() -> Self {
  18         Stack { stack: vec![] }
  19     }
  20 }
  21
  22 index_struct! {
  23     /// The StackIndex identifies the position of a table's goal in the
  24     /// stack of goals that are actively being processed. Note that once a
  25     /// table is completely evaluated, it may be popped from the stack,
  26     /// and hence no longer have a stack index.
  27     pub(crate) struct StackIndex {
  28         value: usize,
  29     }
  30 }
  31
  32 #[derive(Debug)]
  33 pub(crate) struct StackEntry<I: Interner, C: Context<I>> {
  34     /// The goal G from the stack entry `A :- G` represented here.
  35     pub(super) table: TableIndex,
  36
  37     /// The clock TimeStamp of this stack entry.
  38     pub(super) clock: TimeStamp,
  39
  40     pub(super) cyclic_minimums: Minimums,
  41
  42     // FIXME: should store this as an index.
  43     // This would mean that if we unwind,
  44     // we don't need to worry about losing a strand
  45     pub(super) active_strand: Option<Strand<I, C>>,
  46 }
  47
  48 impl<I: Interner, C: Context<I>> Stack<I, C> {
  49     pub(super) fn is_empty(&self) -> bool {
  50         self.stack.is_empty()
  51     }
  52
  53     /// Searches the stack to see if `table` is active. If so, returns
  54     /// its stack index.
  55     pub(super) fn is_active(&self, table: TableIndex) -> Option<StackIndex> {
  56         self.stack
  57             .iter()
  58             .enumerate()
  59             .filter_map(|(index, stack_entry)| {
  60                 if stack_entry.table == table {
  61                     Some(StackIndex::from(index))
  62                 } else {
  63                     None
  64                 }
  65             })
  66             .next()
  67     }
  68
  69     pub(super) fn top_of_stack_from(&self, depth: StackIndex) -> Range<StackIndex> {
  70         depth..StackIndex::from(self.stack.len())
  71     }
  72
  73     pub(super) fn push(
  74         &mut self,
  75         table: TableIndex,
  76         cyclic_minimums: Minimums,
  77         clock: TimeStamp,
  78     ) -> StackIndex {
  79         let old_len = self.stack.len();
  80         self.stack.push(StackEntry {
  81             table,
  82             clock,
  83             cyclic_minimums,
  84             active_strand: None,
  85         });
  86         StackIndex::from(old_len)
  87     }
  88
  89     /// Pops the top-most entry from the stack:
  90     /// * If the stack is now empty, returns false.
  91     /// * Otherwise, returns true.
  92     fn pop_and_adjust_depth(&mut self) -> bool {
  93         self.stack.pop();
  94         !self.stack.is_empty()
  95     }
  96
  97     /// Pops the top-most entry from the stack, which should have the depth `*depth`:
  98     /// * If the stack is now empty, returns None.
  99     /// * Otherwise, `take`s the active strand from the new top and returns it.
 100     pub(super) fn pop_and_take_caller_strand(&mut self) -> Option<Strand<I, C>> {
 101         if self.pop_and_adjust_depth() {
 102             Some(self.top().active_strand.take().unwrap())
 103         } else {
 104             None
 105         }
 106     }
 107
 108     /// Pops the top-most entry from the stack, which should have the depth `*depth`:
 109     /// * If the stack is now empty, returns None.
 110     /// * Otherwise, borrows the active strand (mutably) from the new top and returns it.
 111     pub(super) fn pop_and_borrow_caller_strand(&mut self) -> Option<&mut Strand<I, C>> {
 112         if self.pop_and_adjust_depth() {
 113             Some(self.top().active_strand.as_mut().unwrap())
 114         } else {
 115             None
 116         }
 117     }
 118
 119     pub(super) fn top(&mut self) -> &mut StackEntry<I, C> {
 120         self.stack.last_mut().unwrap()
 121     }
 122 }
 123
 124 impl<I: Interner, C: Context<I>> Index<StackIndex> for Stack<I, C> {
 125     type Output = StackEntry<I, C>;
 126
 127     fn index(&self, index: StackIndex) -> &StackEntry<I, C> {
 128         &self.stack[index.value]
 129     }
 130 }
 131
 132 impl<I: Interner, C: Context<I>> IndexMut<StackIndex> for Stack<I, C> {
 133     fn index_mut(&mut self, index: StackIndex) -> &mut StackEntry<I, C> {
 134         &mut self.stack[index.value]
 135     }
 136 }