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}
;
7 use chalk_ir
::interner
::Interner
;
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
>>,
16 impl<I
: Interner
, C
: Context
<I
>> Default
for Stack
<I
, C
> {
17 fn default() -> Self {
18 Stack { stack: vec![] }
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
{
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
,
37 /// The clock TimeStamp of this stack entry.
38 pub(super) clock
: TimeStamp
,
40 pub(super) cyclic_minimums
: Minimums
,
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
>>,
48 impl<I
: Interner
, C
: Context
<I
>> Stack
<I
, C
> {
49 pub(super) fn is_empty(&self) -> bool
{
53 /// Searches the stack to see if `table` is active. If so, returns
55 pub(super) fn is_active(&self, table
: TableIndex
) -> Option
<StackIndex
> {
59 .filter_map(|(index
, stack_entry
)| {
60 if stack_entry
.table
== table
{
61 Some(StackIndex
::from(index
))
69 pub(super) fn top_of_stack_from(&self, depth
: StackIndex
) -> Range
<StackIndex
> {
70 depth
..StackIndex
::from(self.stack
.len())
76 cyclic_minimums
: Minimums
,
79 let old_len
= self.stack
.len();
80 self.stack
.push(StackEntry
{
86 StackIndex
::from(old_len
)
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
{
94 !self.stack
.is_empty()
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())
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())
119 pub(super) fn top(&mut self) -> &mut StackEntry
<I
, C
> {
120 self.stack
.last_mut().unwrap()
124 impl<I
: Interner
, C
: Context
<I
>> Index
<StackIndex
> for Stack
<I
, C
> {
125 type Output
= StackEntry
<I
, C
>;
127 fn index(&self, index
: StackIndex
) -> &StackEntry
<I
, C
> {
128 &self.stack
[index
.value
]
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
]