scopegraphs/
scopegraph.rs

1use std::cell::{Ref, RefCell};
2use std::{
3    collections::HashSet,
4    fmt::{Debug, Formatter},
5    hash::Hash,
6};
7
8use crate::completeness::{
9    Completeness, Implicit, ScopeExtPerm, UncheckedCompleteness, UserClosed,
10};
11use crate::label::ArrayInit;
12use crate::storage::Storage;
13use crate::Label;
14
15/// Representation of scopes (nodes in the scope graph).
16#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
17pub struct Scope(pub usize);
18
19impl Debug for Scope {
20    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
21        write!(f, "#{}", self.0)
22    }
23}
24
25// Mutability: RefCell in Scope, not Scope in RefCell
26// Concurrency: RW-lock on edges
27
28pub struct InnerScopeGraph<'sg, LABEL: Label, DATA> {
29    pub storage: &'sg Storage,
30    #[allow(clippy::type_complexity)]
31    pub edges: RefCell<Vec<&'sg RefCell<LABEL::Array<HashSet<Scope>>>>>, // FIXME: BTreeMap? Vectors? Whatever?
32    pub data: RefCell<Vec<&'sg DATA>>,
33}
34
35impl<LABEL: Label + Debug, DATA: Debug> Debug for InnerScopeGraph<'_, LABEL, DATA> {
36    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
37        let edges = self.edges.borrow();
38
39        struct Wrapper<F>(F);
40        impl<F: Fn(&mut Formatter) -> std::fmt::Result> Debug for Wrapper<F> {
41            fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
42                self.0(f)
43            }
44        }
45
46        f.debug_struct("InnerScopeGraph")
47            .field(
48                "edges",
49                &Wrapper(|f: &mut Formatter| -> std::fmt::Result {
50                    f.debug_list()
51                        .entries(edges.iter().map(|i| Ref::map(i.borrow(), |i| i.as_ref())))
52                        .finish()
53                }),
54            )
55            .field("data", &*self.data.borrow())
56            .finish()
57    }
58}
59
60impl<'sg, LABEL: Label, DATA> InnerScopeGraph<'sg, LABEL, DATA> {
61    fn new(storage: &'sg Storage) -> Self {
62        Self {
63            storage,
64            edges: RefCell::new(Vec::new()),
65            data: RefCell::new(Vec::new()),
66        }
67    }
68
69    /// Adds a new scope to the graph, with `data` as its associated data.
70    /// After this operation, all future calls to [`InnerScopeGraph::get_data`] on this scope will return the associated data.
71    pub fn add_scope(&self, data: DATA) -> Scope {
72        let id = self.data.borrow().len();
73
74        self.data.borrow_mut().push(self.storage.0.alloc(data));
75        self.edges.borrow_mut().push(
76            self.storage
77                .0
78                .alloc(RefCell::new(LABEL::Array::init_from_fn(HashSet::new))),
79        );
80        Scope(id)
81    }
82
83    /// Returns the data associated with the `scope` argument.
84    fn get_data(&self, scope: Scope) -> &'sg DATA {
85        // panics if src.0 is out of bounds
86        // the methods that update `ScopeGraphs` retain the invariant that each scope has an appropriate entry in this vector
87        // however, panics can still happen when a scope from a different scope graph is used
88        self.data.borrow()[scope.0]
89    }
90}
91
92impl<LABEL: Label, DATA> InnerScopeGraph<'_, LABEL, DATA> {
93    /// Adds a new edge from `src`, to `dst`, with label `lbl` to the scope graph.
94    /// After this operation, all future calls to [`InnerScopeGraph::get_edges`] on the source will contain the destination.
95    pub fn add_edge(&self, src: Scope, lbl: LABEL, dst: Scope) {
96        // panics if src.0 is out of bounds
97        // the methods that update `ScopeGraphs` retain the invariant that each scope has an appropriate entry in this vector
98        // however, panics can still happen when a scope from a different scope graph is used
99        self.edges.borrow()[src.0].borrow_mut().as_mut()[lbl.to_usize()].insert(dst);
100    }
101
102    /// Returns the targets of the outgoing edges of `src` with label `lbl`.
103    pub fn get_edges(&self, scope: Scope, lbl: LABEL) -> Vec<Scope> {
104        // panics if scope.0 is out of bounds
105        // the methods that update `ScopeGraphs` retain the invariant that each scope has an appropriate entry in this vector
106        // however, panics can still happen when a scope from a different scope graph is used
107        self.edges.borrow()[scope.0].borrow().as_ref()[lbl.to_usize()]
108            .iter()
109            .copied()
110            .collect()
111    }
112}
113
114/// Scope Graph data structure.
115///
116/// As a data structure, scope graphs are simple graphs with labeled nodes and labeled, directed edges.
117///
118/// This trait has three type parameters:
119/// - `LABEL`: the type of the edge labels.
120/// - `DATA`: the type of the scope/node labels.
121/// - `CMPL`: metadata that guarantees query stability (i.e., query results remain valid in the future).
122///
123/// The data structure has been designed for typical scope graph usage scenario's.
124/// For example, there is no support for _removing_ scopes or edges, as this usually does not happen in scope graphs.
125/// In addition, there is no data type for edges, as edges should only be traversed, but never leak outside the scope graph structure.
126/// Finally, although not made explicit, `LABEL` should be a finite, iterable set.
127pub struct ScopeGraph<'storage, LABEL: Label, DATA, CMPL> {
128    pub(crate) inner_scope_graph: InnerScopeGraph<'storage, LABEL, DATA>,
129    pub(crate) completeness: CMPL,
130}
131
132impl<LABEL: Label + Debug, DATA: Debug, CMPL: Debug> Debug for ScopeGraph<'_, LABEL, DATA, CMPL> {
133    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
134        f.debug_struct("ScopeGraph")
135            .field("inner_scope_graph", &self.inner_scope_graph)
136            .field("completeness", &self.inner_scope_graph)
137            .finish()
138    }
139}
140
141impl<'storage, LABEL: Label, DATA, CMPL> ScopeGraph<'storage, LABEL, DATA, CMPL> {
142    /// Creates a new, empty, scope graph.
143    ///
144    /// You must supply a [`Storage`] object, in which the scope graph can allocate memory,
145    /// and a [`Completeness`] strategy, that defines how the scope graph should deal with query stability.
146    pub fn new(storage: &'storage Storage, completeness: CMPL) -> Self {
147        ScopeGraph {
148            inner_scope_graph: InnerScopeGraph::new(storage),
149            completeness,
150        }
151    }
152}
153
154impl<'sg, LABEL: Label, DATA> ScopeGraph<'sg, LABEL, DATA, UncheckedCompleteness> {
155    /// Creates a new scope graph with [`UncheckedCompleteness`] as its completeness validation.
156    ///
157    /// # Safety
158    ///
159    /// Unsafe, because [`UncheckedCompleteness`] does not actually guarantee query stability.
160    pub unsafe fn raw(storage: &'sg Storage) -> Self {
161        Self::new(storage, UncheckedCompleteness::new())
162    }
163}
164
165impl<LABEL: Label, DATA, CMPL> ScopeGraph<'_, LABEL, DATA, CMPL>
166where
167    CMPL: Completeness<LABEL, DATA>,
168{
169    /// Add a new scope to the scope graph, with `data` as its label.
170    pub fn add_scope(&self, data: DATA) -> Scope {
171        let scope = self.inner_scope_graph.add_scope(data);
172        self.completeness
173            .cmpl_new_scope(&self.inner_scope_graph, scope);
174        scope
175    }
176
177    // add_edge defined below, based on completeness type
178
179    /// Get the data associated with a scope.
180    pub fn get_data(&self, scope: Scope) -> &DATA {
181        self.inner_scope_graph.get_data(scope)
182    }
183
184    /// Get the targets of the outgoing edges of a scope with some label.
185    ///
186    /// Permission for this operation is checked by `CMPL`.
187    pub fn get_edges(&self, src: Scope, lbl: LABEL) -> CMPL::GetEdgesResult<'_> {
188        self.completeness
189            .cmpl_get_edges(&self.inner_scope_graph, src, lbl)
190    }
191}
192
193impl<LABEL: Label, DATA, CMPL> ScopeGraph<'_, LABEL, DATA, CMPL>
194where
195    CMPL: Implicit<LABEL, DATA>,
196{
197    /// Add a new edge in the scope graph.
198    ///
199    /// Permission for this is checked by `CMPL`.
200    pub fn add_edge(&self, src: Scope, lbl: LABEL, dst: Scope) -> CMPL::NewEdgeResult {
201        self.completeness
202            .cmpl_new_edge(&self.inner_scope_graph, src, lbl, dst)
203    }
204
205    /// Utility function to add declarations (i.e., scopes with data, without any outgoing edges).
206    ///
207    /// It performs (roughly) the following operation:
208    ///
209    /// ```ignore
210    /// fn add_decl(&self, src: Scope, lbl: LABEL, data: DATA) -> CMPL::NewEdgeResult {
211    ///     let s_data = self.add_scope(data);
212    ///     self.add_edge(src, lbl, s_data);
213    /// }
214    /// ```
215    pub fn add_decl(&self, src: Scope, lbl: LABEL, data: DATA) -> CMPL::NewEdgeResult {
216        // Create scope with no open edges.
217        let s_data = self.inner_scope_graph.add_scope(data);
218        self.completeness
219            .cmpl_new_complete_scope(&self.inner_scope_graph, s_data);
220        self.add_edge(src, lbl, s_data)
221    }
222}
223
224impl<LABEL: Hash + Label + Copy + Debug, DATA, CMPL> ScopeGraph<'_, LABEL, DATA, CMPL>
225where
226    CMPL: UserClosed<LABEL, DATA>,
227{
228    /// Add a new edge in the scope graph.
229    ///
230    /// Permission for this is checked by `CMPL`.
231    pub fn ext_edge<'ext>(
232        &'ext self,
233        ext: &ScopeExtPerm<'ext, LABEL, DATA, CMPL>,
234        dst: Scope,
235    ) -> CMPL::NewEdgeResult {
236        self.completeness
237            .cmpl_new_edge(&self.inner_scope_graph, *ext.scope(), *ext.label(), dst)
238    }
239
240    /// Utility function to add declarations (i.e., scopes with data, without any outgoing edges).
241    ///
242    /// It performs (roughly) the following operation:
243    ///
244    /// ```ignore
245    /// fn ext_decl(&self, src: Scope, lbl: LABEL, data: DATA) -> CMPL::NewEdgeResult {
246    ///     let s_data = self.add_scope(data);
247    ///     self.ext_edge(src, lbl, s_data);
248    /// }
249    /// ```
250    pub fn ext_decl<'ext>(
251        &'ext self,
252        ext: &ScopeExtPerm<'ext, LABEL, DATA, CMPL>,
253        data: DATA,
254    ) -> CMPL::NewEdgeResult {
255        // Create scope with no open edges.
256        let s_data = self.inner_scope_graph.add_scope(data);
257        self.completeness
258            .cmpl_new_complete_scope(&self.inner_scope_graph, s_data);
259        self.ext_edge(ext, s_data)
260    }
261}
262
263impl<LABEL: Label, DATA, CMPL> ScopeGraph<'_, LABEL, DATA, CMPL>
264where
265    DATA: Default,
266    CMPL: Completeness<LABEL, DATA>,
267{
268    /// Add a new scope to the scope graph, with default data.
269    pub fn add_scope_default(&self) -> Scope {
270        self.add_scope(DATA::default())
271    }
272}
scopegraphs/scopegraph.rs

scopegraphs/
scopegraph.rs
