macroonz_compiler/relation/
questions.rs

1//! Pure structural questions over already informed relation values.
2//!
3//! These operations compute answers.
4//! The caller separately states which answer is lawful.
5
6use super::{
7    CompletenessPosture, CompletenessStanding, CyclePosture, CycleStanding, DensityPosture,
8    DensityStanding, EmptyPosture, KeyedRosterRows, OccupancyStanding, Reachability,
9    ReachabilityError, ReferencedRosterRow, RepetitionPosture, RepetitionStanding,
10    RosterRelationStanding, RowOrder, SameRosterRequired, SelfRelationPosture,
11    SelfRelationStanding, StructuralMismatch, StructuralRequirement,
12};
13use crate::bounded::{Bounded, NonEmpty};
14
15impl<Answer> StructuralRequirement<Answer> {
16    /// States the exact answer one caller requires from one structural question.
17    pub const fn stated(required: Answer) -> Self {
18        Self { required }
19    }
20
21    /// The answer the caller requires.
22    #[must_use]
23    pub const fn required(&self) -> &Answer {
24        &self.required
25    }
26}
27
28impl<Answer: Eq> StructuralRequirement<Answer> {
29    /// Settles one computed answer against this caller-declared requirement.
30    ///
31    /// # Errors
32    ///
33    /// Returns both answers when the computed answer differs from the required answer.
34    pub fn settle(self, observed: Answer) -> Result<Answer, StructuralMismatch<Answer>> {
35        if self.required == observed {
36            Ok(observed)
37        } else {
38            Err(StructuralMismatch {
39                required: self.required,
40                observed,
41            })
42        }
43    }
44}
45
46impl<Answer> StructuralMismatch<Answer> {
47    /// The answer the caller required.
48    #[must_use]
49    pub const fn required(&self) -> &Answer {
50        &self.required
51    }
52
53    /// The answer the structural question computed.
54    #[must_use]
55    pub const fn observed(&self) -> &Answer {
56        &self.observed
57    }
58}
59
60impl EmptyPosture {
61    /// The occupancy requirement expressed by this posture, when it constrains occupancy.
62    #[must_use]
63    pub const fn requirement(self) -> Option<StructuralRequirement<OccupancyStanding>> {
64        match self {
65            Self::Allowed => None,
66            Self::Refusal => Some(StructuralRequirement::stated(OccupancyStanding::Populated)),
67        }
68    }
69}
70
71impl RepetitionPosture {
72    /// The repetition requirement expressed by this posture, when it constrains repetition.
73    #[must_use]
74    pub const fn requirement(self) -> Option<StructuralRequirement<RepetitionStanding>> {
75        match self {
76            Self::Allowed => None,
77            Self::Refusal => Some(StructuralRequirement::stated(RepetitionStanding::Distinct)),
78        }
79    }
80}
81
82impl CompletenessPosture {
83    /// The completeness requirement expressed by this posture, when it constrains coverage.
84    #[must_use]
85    pub const fn requirement(self) -> Option<StructuralRequirement<CompletenessStanding>> {
86        match self {
87            Self::Partial => None,
88            Self::Total => Some(StructuralRequirement::stated(
89                CompletenessStanding::Complete,
90            )),
91        }
92    }
93}
94
95impl DensityPosture {
96    /// The density requirement expressed by this posture, when it constrains pair coverage.
97    #[must_use]
98    pub const fn requirement(self) -> Option<StructuralRequirement<DensityStanding>> {
99        match self {
100            Self::Sparse => None,
101            Self::Dense => Some(StructuralRequirement::stated(DensityStanding::Dense)),
102        }
103    }
104}
105
106impl SelfRelationPosture {
107    /// The self-relation requirement expressed by this posture, when it constrains self relations.
108    #[must_use]
109    pub const fn requirement(self) -> Option<StructuralRequirement<SelfRelationStanding>> {
110        match self {
111            Self::Allowed => None,
112            Self::Refusal => Some(StructuralRequirement::stated(SelfRelationStanding::Absent)),
113        }
114    }
115}
116
117impl CyclePosture {
118    /// The cycle requirement expressed by this posture, when it constrains cycles.
119    #[must_use]
120    pub const fn requirement(self) -> Option<StructuralRequirement<CycleStanding>> {
121        match self {
122            Self::Allowed => None,
123            Self::Refusal => Some(StructuralRequirement::stated(CycleStanding::Acyclic)),
124        }
125    }
126}
127
128impl<const N: usize> Reachability<N> {
129    /// Reachable roster positions in roster order.
130    pub fn reachable_positions(&self) -> impl Iterator<Item = usize> + '_ {
131        self.reachable.iter().copied()
132    }
133
134    /// Unreachable roster positions in roster order.
135    pub fn unreachable_positions(&self) -> impl Iterator<Item = usize> + '_ {
136        self.unreachable.iter().copied()
137    }
138
139    /// Whether every member is reachable from the declared root.
140    #[must_use]
141    pub fn standing(&self) -> CompletenessStanding {
142        if self.unreachable.is_empty() {
143            CompletenessStanding::Complete
144        } else {
145            CompletenessStanding::Partial
146        }
147    }
148}
149
150impl<
151    Left,
152    LeftKey,
153    Right,
154    RightKey,
155    Payload,
156    const LEFT: usize,
157    const RIGHT: usize,
158    const ROWS: usize,
159> KeyedRosterRows<'_, Left, LeftKey, Right, RightKey, Payload, LEFT, RIGHT, ROWS>
160{
161    /// Reads one row under the caller-selected stable order.
162    #[must_use]
163    pub fn at_in(
164        &self,
165        order: RowOrder,
166        index: usize,
167    ) -> Option<(&LeftKey, &Left, &RightKey, &Right, &Payload)> {
168        match order {
169            RowOrder::Authored => self.at(index),
170            RowOrder::Canonical => self.canonical_at(index),
171        }
172    }
173
174    /// Whether this relation holds no row or at least one.
175    #[must_use]
176    pub fn occupancy_standing(&self) -> OccupancyStanding {
177        if self.is_empty() {
178            OccupancyStanding::Empty
179        } else {
180            OccupancyStanding::Populated
181        }
182    }
183
184    /// Whether every endpoint pair occurs once or at least one pair repeats.
185    #[must_use]
186    pub fn repetition_standing(&self) -> RepetitionStanding {
187        let repeated = self.rows.iter().enumerate().any(|(position, row)| {
188            self.rows
189                .iter()
190                .skip(position.saturating_add(1))
191                .any(|later| {
192                    later.left_position == row.left_position
193                        && later.right_position == row.right_position
194                })
195        });
196        if repeated {
197            RepetitionStanding::Repeated
198        } else {
199            RepetitionStanding::Distinct
200        }
201    }
202
203    /// Whether every left-roster member occurs in at least one row.
204    #[must_use]
205    pub fn left_completeness(&self) -> CompletenessStanding {
206        completeness_over(self.left.count(), |position| {
207            self.rows.iter().any(|row| row.left_position == position)
208        })
209    }
210
211    /// Whether every right-roster member occurs in at least one row.
212    #[must_use]
213    pub fn right_completeness(&self) -> CompletenessStanding {
214        completeness_over(self.right.count(), |position| {
215            self.rows.iter().any(|row| row.right_position == position)
216        })
217    }
218
219    /// Whether every pair in the left-by-right roster product occurs in at least one row.
220    #[must_use]
221    pub fn density_standing(&self) -> DensityStanding {
222        let dense = (0..self.left.count()).all(|left_position| {
223            (0..self.right.count())
224                .all(|right_position| pair_is_present(&self.rows, left_position, right_position))
225        });
226        if dense {
227            DensityStanding::Dense
228        } else {
229            DensityStanding::Sparse
230        }
231    }
232}
233
234impl<Member, Key, Payload, const MEMBERS: usize, const ROWS: usize>
235    KeyedRosterRows<'_, Member, Key, Member, Key, Payload, MEMBERS, MEMBERS, ROWS>
236{
237    /// Whether both relation sides borrow the same roster instance.
238    #[must_use]
239    pub fn roster_relation_standing(&self) -> RosterRelationStanding {
240        if core::ptr::eq(self.left, self.right) {
241            RosterRelationStanding::Same
242        } else {
243            RosterRelationStanding::Cross
244        }
245    }
246
247    /// Whether at least one row relates a member to itself.
248    ///
249    /// # Errors
250    ///
251    /// Returns a typed refusal when the relation sides borrow different roster instances.
252    pub fn self_relation_standing(&self) -> Result<SelfRelationStanding, SameRosterRequired> {
253        self.require_same_roster()?;
254        if self
255            .rows
256            .iter()
257            .any(|row| row.left_position == row.right_position)
258        {
259            Ok(SelfRelationStanding::Present)
260        } else {
261            Ok(SelfRelationStanding::Absent)
262        }
263    }
264
265    /// Whether this same-roster directed relation contains a cycle.
266    ///
267    /// # Errors
268    ///
269    /// Returns a typed refusal when the relation sides borrow different roster instances.
270    pub fn cycle_standing(&self) -> Result<CycleStanding, SameRosterRequired> {
271        self.require_same_roster()?;
272        if (0..self.left.count()).any(|root| self.path_returns_to(root)) {
273            Ok(CycleStanding::Cyclic)
274        } else {
275            Ok(CycleStanding::Acyclic)
276        }
277    }
278
279    fn require_same_roster(&self) -> Result<(), SameRosterRequired> {
280        match self.roster_relation_standing() {
281            RosterRelationStanding::Same => Ok(()),
282            RosterRelationStanding::Cross => Err(SameRosterRequired),
283        }
284    }
285
286    fn path_returns_to(&self, root: usize) -> bool {
287        let mut discovered = vec![root];
288        let mut cursor = 0_usize;
289        while let Some(position) = discovered.get(cursor).copied() {
290            if self.advance_cycle_search(position, root, &mut discovered) {
291                return true;
292            }
293            cursor = cursor.saturating_add(1);
294        }
295        false
296    }
297
298    fn advance_cycle_search(
299        &self,
300        position: usize,
301        root: usize,
302        discovered: &mut Vec<usize>,
303    ) -> bool {
304        for destination in self.destinations_from(position) {
305            if destination == root {
306                return true;
307            }
308            retain_once(discovered, destination);
309        }
310        false
311    }
312
313    fn extend_reachability(&self, position: usize, discovered: &mut Vec<usize>) {
314        for destination in self.destinations_from(position) {
315            retain_once(discovered, destination);
316        }
317    }
318
319    fn destinations_from(&self, position: usize) -> impl Iterator<Item = usize> + '_ {
320        self.rows
321            .iter()
322            .filter(move |row| row.left_position == position)
323            .map(|row| row.right_position)
324    }
325}
326
327impl<Member, Key: Eq, Payload, const MEMBERS: usize, const ROWS: usize>
328    KeyedRosterRows<'_, Member, Key, Member, Key, Payload, MEMBERS, MEMBERS, ROWS>
329{
330    /// Partitions one shared roster into members reachable and unreachable from a declared root.
331    ///
332    /// Both partitions follow roster order rather than traversal order.
333    ///
334    /// # Errors
335    ///
336    /// Returns a typed refusal when the relation sides borrow different roster instances or when the root is outside that roster.
337    pub fn reachability_from(
338        &self,
339        root: Key,
340    ) -> Result<Reachability<MEMBERS>, ReachabilityError<Key>> {
341        self.require_same_roster()
342            .map_err(ReachabilityError::DifferentRosters)?;
343        let Some(root_position) = self.left.index_of(&root) else {
344            return Err(ReachabilityError::RootOutsideRoster { root });
345        };
346        let discovered = self.discover_from(root_position);
347        let reachable = self
348            .left
349            .positions_where(|position, _, _| discovered.contains(&position));
350        let unreachable = self
351            .left
352            .positions_where(|position, _, _| !discovered.contains(&position));
353        let reachable = NonEmpty::from_bounded(reachable)
354            .map_err(|_| ReachabilityError::RootOutsideRoster { root })?;
355        Ok(Reachability {
356            reachable,
357            unreachable,
358        })
359    }
360
361    fn discover_from(&self, root: usize) -> Vec<usize> {
362        let mut discovered = vec![root];
363        let mut cursor = 0_usize;
364        while let Some(position) = discovered.get(cursor).copied() {
365            self.extend_reachability(position, &mut discovered);
366            cursor = cursor.saturating_add(1);
367        }
368        discovered
369    }
370}
371
372fn pair_is_present<Left, LeftKey, Right, RightKey, Payload, const N: usize>(
373    rows: &Bounded<ReferencedRosterRow<'_, Left, LeftKey, Right, RightKey, Payload>, N>,
374    left_position: usize,
375    right_position: usize,
376) -> bool {
377    rows.iter()
378        .any(|row| row.left_position == left_position && row.right_position == right_position)
379}
380
381fn retain_once(held: &mut Vec<usize>, position: usize) {
382    if held.contains(&position) {
383        return;
384    }
385    held.push(position);
386}
387
388fn completeness_over(
389    positions: usize,
390    mut contains: impl FnMut(usize) -> bool,
391) -> CompletenessStanding {
392    if (0..positions).all(&mut contains) {
393        CompletenessStanding::Complete
394    } else {
395        CompletenessStanding::Partial
396    }
397}
macroonz_compiler/relation/questions.rs

macroonz_compiler/relation/
questions.rs
