Skip to main content

dive_value/
subset_cursor.rs

1//! Transactional integer positions for an already prepared concrete powerset.
2
3use super::SubsetIter;
4use crate::{ErrorKind, Result, Set, Value, ValueError};
5
6/// A concrete powerset stream retaining its original normalized base and order.
7///
8/// Preparing an index restriction does not consume this stream. A prepared
9/// commit only swaps integer storage; constructing its next Value stays separate.
10/// No permission, predicate truth or ownership authority follows from this API.
11///
12/// ```
13/// use dive_value::{Ctx, Value, SubsetScratch};
14/// let ctx = Ctx::tlc();
15/// let Value::Set(set) = Value::subset(Value::interval(1.into(), 3.into(), ctx), ctx)
16///     else { return Err("set".into()); };
17/// let mut stream = set.concrete_subset_stream(ctx)?.ok_or("concrete base")?;
18/// assert_eq!(stream.next(), Some(Value::empty_set(ctx)));
19/// let mut scratch = SubsetScratch::default();
20/// assert!(stream.prepare_masked_next(&[0, 2], &mut scratch, || Ok(()))?);
21/// scratch.prepare_commit(&mut stream).ok_or("position changed")?.commit();
22/// assert_eq!(stream.current_indices(), None); // next Value has not been built
23/// assert!(stream.next().is_some());
24/// assert_eq!(stream.current_indices(), Some([0].as_slice()));
25/// # Ok::<(), Box<dyn std::error::Error>>(())
26/// ```
27pub struct ConcreteSubsetStream {
28    source: Set,
29    inner: SubsetIter,
30    pending: bool,
31    done: bool,
32}
33
34#[derive(Default)]
35struct Position {
36    indices: Vec<usize>,
37    k: usize,
38    started: bool,
39    pending: bool,
40    done: bool,
41}
42
43/// Reusable preparation storage containing integers only, never Value owners.
44/// A failed or cancelled preparation leaves the original stream untouched.
45#[derive(Default)]
46pub struct SubsetScratch {
47    from: Position,
48    target: Position,
49    base_len: usize,
50    ready: bool,
51}
52
53/// An exclusively borrowed commit, validated before any caller acquires a lock.
54/// Dropping it without committing leaves the original stream unchanged.
55/// `commit` does not allocate, deallocate, build/drop a Value or invoke a callback.
56pub struct SubsetCommit<'a> {
57    stream: &'a mut ConcreteSubsetStream,
58    scratch: &'a mut SubsetScratch,
59}
60
61impl ConcreteSubsetStream {
62    pub(super) fn new(inner: SubsetIter, source: Set) -> Self {
63        Self {
64            source,
65            inner,
66            pending: false,
67            done: false,
68        }
69    }
70
71    /// Whether this cursor was prepared from this exact immutable set owner.
72    /// This identifies enumeration data, not predicate or host authority.
73    #[must_use]
74    pub fn belongs_to(&self, source: &Set) -> bool {
75        self.source.ptr_eq(source)
76    }
77
78    /// The actual retained normalized component, with no enumeration or callback.
79    #[must_use]
80    pub fn base_elements(&self) -> &[Value] {
81        &self.inner.base
82    }
83
84    /// Original base indices of the last built candidate. A pending committed
85    /// target has not yet built a candidate and returns `None`.
86    #[must_use]
87    pub fn current_indices(&self) -> Option<&[usize]> {
88        (self.inner.started && !self.pending && !self.done).then_some(self.inner.idx.as_slice())
89    }
90
91    /// Prepare the next subset using only `allowed` base indices, without
92    /// consuming anything. `allowed` must be strictly increasing/in range.
93    /// The requested order is the retained subsequence of the original size/lex
94    /// order, strictly after the last built candidate. A pending/end/unstarted
95    /// stream returns `false`. Preparation and its polling occur outside locks.
96    ///
97    /// # Errors
98    /// Invalid explicit indices, failed scratch reservation or the original
99    /// error returned by `poll`; no cursor position is changed on any error.
100    pub fn prepare_masked_next(
101        &self,
102        allowed: &[usize],
103        scratch: &mut SubsetScratch,
104        mut poll: impl FnMut() -> Result<()>,
105    ) -> Result<bool> {
106        scratch.ready = false;
107        let Some(current) = self.current_indices() else {
108            return Ok(false);
109        };
110        poll()?;
111        let mut previous = None;
112        for &index in allowed {
113            poll()?;
114            if index >= self.inner.base.len() || previous.is_some_and(|p| p >= index) {
115                return Err(ValueError::new(
116                    ErrorKind::Argument,
117                    "subset indices must be increasing and in range",
118                ));
119            }
120            previous = Some(index);
121        }
122        copy_indices(&mut scratch.from.indices, current, &mut poll)?;
123        scratch.from.k = self.inner.k;
124        scratch.from.started = self.inner.started;
125        scratch.from.pending = self.pending;
126        scratch.from.done = self.done;
127        scratch.base_len = self.inner.base.len();
128        scratch.target.indices.clear();
129        scratch
130            .target
131            .indices
132            .try_reserve(allowed.len())
133            .map_err(|error| reservation(&error))?;
134        let k = current.len();
135        let ranks = &mut scratch.target.indices;
136        let mut greater = false;
137        if k <= allowed.len() {
138            for (position, &index) in current.iter().enumerate() {
139                poll()?;
140                let lower = allowed.partition_point(|candidate| *candidate < index);
141                let rank = ranks.last().map_or(lower, |last| lower.max(last + 1));
142                if rank >= allowed.len() || allowed.len() - rank < k - position {
143                    break;
144                }
145                ranks.push(rank);
146                if allowed[rank] > index {
147                    greater = true;
148                    fill_ranks(ranks, k, &mut poll)?;
149                    break;
150                }
151            }
152        }
153        if !greater {
154            // Equal prefix (possibly complete): carry right to left. A strict
155            // successor is needed even when the current tuple is fully allowed.
156            while let Some(last) = ranks.last().copied() {
157                poll()?;
158                let position = ranks.len() - 1;
159                if last < allowed.len() - k + position {
160                    ranks[position] += 1;
161                    fill_ranks(ranks, k, &mut poll)?;
162                    greater = true;
163                    break;
164                }
165                ranks.pop();
166            }
167        }
168        if !greater {
169            ranks.clear();
170            if k < allowed.len() {
171                for rank in 0..=k {
172                    poll()?;
173                    ranks.push(rank);
174                }
175            } else {
176                scratch.target.done = true;
177                scratch.target.pending = false;
178                scratch.target.started = true;
179                scratch.target.k = k;
180                scratch.ready = true;
181                return Ok(true);
182            }
183        }
184        for rank in ranks.iter_mut() {
185            poll()?;
186            *rank = allowed[*rank];
187        }
188        scratch.target.k = ranks.len();
189        scratch.target.started = true;
190        scratch.target.pending = true;
191        scratch.target.done = false;
192        scratch.ready = true;
193        Ok(true)
194    }
195}
196
197fn reservation(error: &std::collections::TryReserveError) -> ValueError {
198    ValueError::new(
199        ErrorKind::DiveLimit,
200        format!("subset index scratch: {error}"),
201    )
202}
203fn copy_indices(
204    to: &mut Vec<usize>,
205    from: &[usize],
206    poll: &mut impl FnMut() -> Result<()>,
207) -> Result<()> {
208    to.clear();
209    to.try_reserve(from.len())
210        .map_err(|error| reservation(&error))?;
211    for &index in from {
212        poll()?;
213        to.push(index);
214    }
215    Ok(())
216}
217fn fill_ranks(
218    ranks: &mut Vec<usize>,
219    length: usize,
220    poll: &mut impl FnMut() -> Result<()>,
221) -> Result<()> {
222    while ranks.len() < length {
223        poll()?;
224        let next = ranks.last().map_or(0, |last| last + 1);
225        ranks.push(next);
226    }
227    Ok(())
228}
229
230impl SubsetScratch {
231    /// Validate the prepared position value/base length and borrow exclusively
232    /// before locking. This is not a source-identity certificate; a caller
233    /// binding predicate truth must also match [`ConcreteSubsetStream::belongs_to`].
234    /// The returned token contains references only, not Value owners.
235    #[must_use]
236    pub fn prepare_commit<'a>(
237        &'a mut self,
238        stream: &'a mut ConcreteSubsetStream,
239    ) -> Option<SubsetCommit<'a>> {
240        if !self.ready
241            || self.base_len != stream.inner.base.len()
242            || self.from.k != stream.inner.k
243            || self.from.started != stream.inner.started
244            || self.from.pending != stream.pending
245            || self.from.done != stream.done
246            || self.from.indices != stream.inner.idx
247        {
248            return None;
249        }
250        Some(SubsetCommit {
251            stream,
252            scratch: self,
253        })
254    }
255}
256
257impl SubsetCommit<'_> {
258    /// Commit a previously prepared position in bounded constant work. Old
259    /// integer scratch remains owned by the caller and is not freed here.
260    pub fn commit(self) {
261        std::mem::swap(&mut self.stream.inner.idx, &mut self.scratch.target.indices);
262        self.stream.inner.k = self.scratch.target.k;
263        self.stream.inner.started = self.scratch.target.started;
264        self.stream.pending = self.scratch.target.pending;
265        self.stream.done = self.scratch.target.done;
266        self.scratch.ready = false;
267    }
268}
269
270impl Iterator for ConcreteSubsetStream {
271    type Item = Value;
272    fn next(&mut self) -> Option<Value> {
273        if self.done {
274            return None;
275        }
276        if self.pending {
277            self.pending = false;
278            return Some(self.inner.current_value());
279        }
280        let value = self.inner.next();
281        if value.is_none() {
282            self.done = true;
283        }
284        value
285    }
286}
287
288#[cfg(test)]
289#[path = "subset_cursor_tests.rs"]
290mod tests;