scopegraphs_lib/completeness/
critical_edge.rs

1use crate::{completeness::Completeness, Scope, ScopeGraph};
2use std::cell::RefCell;
3use std::{collections::HashSet, hash::Hash};
4
5#[derive(Debug)]
6pub(super) struct CriticalEdgeSet<LABEL> {
7    open_edges: RefCell<Vec<HashSet<LABEL>>>,
8}
9
10impl<LABEL> Default for CriticalEdgeSet<LABEL> {
11    fn default() -> Self {
12        Self {
13            open_edges: Default::default(),
14        }
15    }
16}
17
18impl<LABEL> CriticalEdgeSet<LABEL> {
19    pub(super) fn init_scope(&self, edges: HashSet<LABEL>) {
20        self.open_edges.borrow_mut().push(edges)
21    }
22}
23
24impl<LABEL: Hash + Eq> CriticalEdgeSet<LABEL> {
25    pub fn is_open(&self, scope: Scope, lbl: &LABEL) -> bool {
26        self.open_edges.borrow()[scope.0].contains(lbl)
27    }
28
29    pub(super) fn close(&self, scope: Scope, lbl: &LABEL) -> bool {
30        self.open_edges.borrow_mut()[scope.0].remove(lbl)
31    }
32}
33
34/// Sub-trait of [`Completeness`] that uses _critical edges_ (scope-label pairs) to manage completeness.
35///
36/// Provides utility function to create scopes with particular open edges.
37///
38/// Should not be called externally, but only from utility function on [`super::ScopeGraph`].
39pub trait CriticalEdgeBasedCompleteness<LABEL, DATA>: Completeness<LABEL, DATA> {
40    fn init_scope_with(&self, open_edges: HashSet<LABEL>);
41}
42
43/// Error returned when attempting to add an edge with a label that is already closed in that scope.
44#[derive(Debug)]
45pub struct EdgeClosedError<LABEL> {
46    pub scope: Scope,
47    pub label: LABEL,
48}
49
50/// Value returned when a query cannot yet be computed because some edge it depends on is still closed.
51#[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)]
52pub struct Delay<LABEL> {
53    pub scope: Scope,
54    pub label: LABEL,
55}
56
57pub(crate) type EdgesOrDelay<EDGES, LABEL> = Result<EDGES, Delay<LABEL>>;
58
59impl<'sg, LABEL: Hash + Eq, DATA, CMPL> ScopeGraph<'sg, LABEL, DATA, CMPL>
60where
61    CMPL: CriticalEdgeBasedCompleteness<LABEL, DATA>,
62{
63    /// Adds a new scope with some open edges.
64    pub fn add_scope_with<I>(&mut self, data: DATA, open_edges: I) -> Scope
65    where
66        I: IntoIterator<Item = LABEL>,
67    {
68        let scope = self.inner_scope_graph.add_scope(data);
69        self.completeness
70            .init_scope_with(open_edges.into_iter().collect());
71        scope
72    }
73
74    /// Adds a new scope with no open edges.
75    pub fn add_scope_closed(&mut self, data: DATA) -> Scope {
76        let scope = self.inner_scope_graph.add_scope(data);
77        self.completeness.init_scope_with(HashSet::new());
78        scope
79    }
80}
81
82impl<'sg, LABEL: Hash + Eq, DATA, CMPL> ScopeGraph<'sg, LABEL, DATA, CMPL>
83where
84    DATA: Default,
85    CMPL: CriticalEdgeBasedCompleteness<LABEL, DATA>,
86{
87    /// Adds a new scope with some open edges and default data.
88    pub fn add_scope_default_with<I>(&mut self, open_edges: I) -> Scope
89    where
90        I: IntoIterator<Item = LABEL>,
91    {
92        self.add_scope_with(DATA::default(), open_edges)
93    }
94
95    /// Adds a new scope with no open edges and default data.
96    pub fn add_scope_default_closed(&mut self) -> Scope {
97        self.add_scope_with(DATA::default(), HashSet::new())
98    }
99}
scopegraphs_lib/completeness/critical_edge.rs

scopegraphs_lib/completeness/
critical_edge.rs
