scopegraphs/completeness/
critical_edge.rs

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

scopegraphs/completeness/
critical_edge.rs
