scopegraphs_lib/resolve/
mod.rs

1use scopegraphs_prust_lib::hashmap::HashSet as TrieSet;
2use std::collections::HashSet;
3use std::fmt::{Debug, Formatter};
4use std::hash::Hash;
5use std::marker::PhantomData;
6use std::rc::Rc;
7
8use super::{Scope, ScopeGraph};
9
10mod params;
11pub use params::*;
12use scopegraphs_regular_expressions::RegexMatcher;
13
14pub mod lookup;
15
16/// Representation of either a labeled edge or the special 'data' label.
17///
18/// Used to implement label orders. The `Data` label is there to support expressing preference
19/// between traversing an edge or resolving to the current node.
20#[derive(Hash, PartialEq, Eq)]
21pub enum EdgeOrData<LABEL> {
22    Data,
23    Edge(LABEL),
24}
25
26impl<LABEL: Debug> Debug for EdgeOrData<LABEL> {
27    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
28        match self {
29            EdgeOrData::Data => write!(f, "$"),
30            EdgeOrData::Edge(lbl) => write!(f, "@{:?}", lbl),
31        }
32    }
33}
34
35// custom implementation not to impose LABEL: Copy
36impl<LABEL: Copy> Clone for EdgeOrData<LABEL> {
37    fn clone(&self) -> Self {
38        *self
39    }
40}
41
42impl<LABEL: Copy> Copy for EdgeOrData<LABEL> {}
43
44#[derive(Hash, PartialEq, Eq, Debug)]
45enum InnerPath<LABEL> {
46    Start {
47        source: Scope,
48    },
49    Step {
50        prefix: Path<LABEL>,
51        label: LABEL,
52        target: Scope,
53    },
54}
55
56/// Path (alternating sequence of scopes and labels) in a scope graph.
57#[derive(Clone)]
58pub struct Path<LABEL> {
59    inner_path: Rc<InnerPath<LABEL>>,
60    /// Set of all scopes in this path.
61    ///
62    /// Paths are alternating sequences of scopes and labels.
63    /// In scope graphs, paths may not be cyclic.
64    /// To check whether a possible _path extension_ is cyclic, we maintain a separate set of all scopes in a path.
65    /// The [`Path::step`] function will check whether the new scope is in this set, and only return an extended oath if this is not the case.
66    /// This is cheaper than traversing the [`Path::inner_path`], at the cost of some more memory usage.
67    ///
68    /// In order to make paths cheap to extend multiple times, we use a persistent data structure.
69    scopes: Rc<TrieSet<Scope>>,
70    // FIXME: put fields in same Arc
71}
72
73impl<LABEL> PartialEq for Path<LABEL>
74where
75    Scope: PartialEq,
76    LABEL: PartialEq,
77{
78    fn eq(&self, other: &Self) -> bool {
79        // `self.scopes` is determined by the `inner_path`, so no need to check for equality there.
80        self.inner_path == other.inner_path
81    }
82}
83
84impl<LABEL> Eq for Path<LABEL>
85where
86    Scope: Eq,
87    LABEL: Eq,
88{
89}
90
91impl<LABEL> Hash for Path<LABEL>
92where
93    Scope: Hash,
94    LABEL: Hash,
95{
96    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
97        // `self.scopes` is determined by the `inner_path`, so no need to separately hash it.
98        self.inner_path.hash(state);
99    }
100}
101
102impl<LABEL> Debug for Path<LABEL>
103where
104    LABEL: Debug,
105{
106    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
107        f.debug_struct("Path")
108            // `self.scopes` is determined by the `inner_path`, so no need to include it in the debug representation.
109            .field("inner_path", &self.inner_path)
110            .finish()
111    }
112}
113
114/// A path in the scope graph, including the data of the target of the path.
115#[derive(Hash, PartialEq, Eq, Debug)]
116pub struct ResolvedPath<'sg, LABEL, DATA> {
117    path: Path<LABEL>,
118    data: &'sg DATA,
119}
120
121impl<'sg, LABEL: Clone, DATA> Clone for ResolvedPath<'sg, LABEL, DATA> {
122    fn clone(&self) -> Self {
123        Self {
124            path: self.path.clone(),
125            data: self.data,
126        }
127    }
128}
129
130impl<'sg, LABEL, DATA> ResolvedPath<'sg, LABEL, DATA> {
131    pub fn path(&self) -> &Path<LABEL> {
132        &self.path
133    }
134
135    pub fn data(&self) -> &DATA {
136        self.data
137    }
138}
139
140impl<LABEL> Path<LABEL> {
141    /// Creates a new path that contains of a single scope.
142    pub fn new(source: Scope) -> Self {
143        Self {
144            inner_path: Rc::new(InnerPath::Start { source }),
145            scopes: Rc::new(TrieSet::new().insert(source)),
146        }
147    }
148
149    /// Returns the last scope in the path.
150    pub fn target(&self) -> Scope {
151        match self.inner_path.as_ref() {
152            InnerPath::Start { source } => *source,
153            InnerPath::Step { target, .. } => *target,
154        }
155    }
156
157    /// Extends the path with a new edge.
158    ///
159    /// Returns `None` if the resulting path would contain a cycle.
160    pub fn step(&self, label: LABEL, target: Scope) -> Option<Self> {
161        if self.scopes.search(&target) {
162            None
163        } else {
164            Some(Self {
165                inner_path: Rc::new(InnerPath::Step {
166                    prefix: Self {
167                        inner_path: self.inner_path.clone(),
168                        scopes: self.scopes.clone(),
169                    },
170                    label,
171                    target,
172                }),
173                scopes: Rc::new(self.scopes.insert(target)),
174            })
175        }
176    }
177
178    /// Creates a resolved path from this path.
179    pub fn resolve<DATA>(self, data: &DATA) -> ResolvedPath<'_, LABEL, DATA> {
180        ResolvedPath { path: self, data }
181    }
182}
183
184/// Representation of an environment (i.e., a collection of resolved paths).
185// For now, we stick with hashmaps because they are easy.
186// We might however want to change that in the future, because:
187// - we currently create a lot of new hashmaps, which is not really efficient
188// - efficiency might be dependent on the name resolution (shadowing) strategy
189// - we (not always necessarily) clone hashmaps often
190// Perhaps we will resort to fibbonacy heaps/pairing heaps, and/or make resolution parametric in the environment type.
191#[derive(Debug)]
192pub struct Env<'sg, LABEL: 'sg, DATA>(HashSet<ResolvedPath<'sg, LABEL, DATA>>);
193
194impl<'sg, LABEL, DATA> IntoIterator for Env<'sg, LABEL, DATA> {
195    type Item = ResolvedPath<'sg, LABEL, DATA>;
196
197    type IntoIter = <HashSet<ResolvedPath<'sg, LABEL, DATA>> as IntoIterator>::IntoIter;
198
199    fn into_iter(self) -> Self::IntoIter {
200        self.0.into_iter()
201    }
202}
203
204impl<LABEL, DATA> Default for Env<'_, LABEL, DATA> {
205    fn default() -> Self {
206        Self::new()
207    }
208}
209
210impl<'sg, LABEL, DATA> Env<'sg, LABEL, DATA> {
211    /// Creates an empty environemnt.
212    pub fn new() -> Self {
213        Self(HashSet::new())
214    }
215
216    /// Create an iterator over all paths in the environment.
217    pub fn iter<'a>(&'a self) -> impl Iterator<Item = &'a ResolvedPath<'sg, LABEL, DATA>> + 'a {
218        self.0.iter()
219    }
220
221    /// Returns `true` is the environment is empty, `false` otherwise.
222    pub fn is_empty(&self) -> bool {
223        self.0.is_empty()
224    }
225}
226
227impl<'sg, LABEL, DATA> Env<'sg, LABEL, DATA>
228where
229    ResolvedPath<'sg, LABEL, DATA>: Eq + Hash + Clone,
230{
231    /// Create an environment with a single path.
232    pub fn single(path: ResolvedPath<'sg, LABEL, DATA>) -> Self {
233        let mut env = Env::new();
234        env.insert(path);
235        env
236    }
237
238    /// Insert a path in the environment.
239    pub fn insert(&mut self, path: ResolvedPath<'sg, LABEL, DATA>) {
240        self.0.insert(path);
241    }
242
243    /// Add all paths in `other` to the current environment.
244    pub fn merge(&mut self, other: &Self) {
245        self.0.extend(other.0.iter().cloned())
246    }
247}
248
249impl<'sg, LABEL: 'sg, DATA: Hash> FromIterator<ResolvedPath<'sg, LABEL, DATA>>
250    for Env<'sg, LABEL, DATA>
251where
252    ResolvedPath<'sg, LABEL, DATA>: Eq + Hash,
253{
254    fn from_iter<T: IntoIterator<Item = ResolvedPath<'sg, LABEL, DATA>>>(iter: T) -> Self {
255        Env(HashSet::from_iter(iter))
256    }
257}
258
259impl<'sg, LABEL: 'sg, DATA: Hash> FromIterator<Env<'sg, LABEL, DATA>> for Env<'sg, LABEL, DATA>
260where
261    ResolvedPath<'sg, LABEL, DATA>: Eq + Hash,
262{
263    fn from_iter<T: IntoIterator<Item = Env<'sg, LABEL, DATA>>>(iter: T) -> Self {
264        iter.into_iter().flatten().collect()
265    }
266}
267
268impl<'sg, LABEL: 'sg + Clone, DATA> Clone for Env<'sg, LABEL, DATA> {
269    fn clone(&self) -> Self {
270        Env(self.0.clone())
271    }
272}
273
274pub trait Resolve<'sg, 'rslv> {
275    type EnvContainer
276    where
277        'sg: 'rslv,
278        Self: 'rslv;
279
280    fn resolve(&'rslv self, scope: Scope) -> Self::EnvContainer;
281}
282
283pub struct Query<'storage, 'sg, 'rslv, LABEL, DATA, CMPL, PWF, DWF, LO, DEq> {
284    _phantom: PhantomData<&'rslv ()>,
285    scope_graph: &'sg ScopeGraph<'storage, LABEL, DATA, CMPL>,
286    path_wellformedness: PWF,
287    data_wellformedness: DWF,
288    label_order: LO,
289    data_equivalence: DEq,
290}
291
292impl<'sg, 'storage, 'rslv, LABEL, DATA, CMPL, PWF, DWF, LO, DEq>
293    Query<'sg, 'storage, 'rslv, LABEL, DATA, CMPL, PWF, DWF, LO, DEq>
294{
295    pub fn with_path_wellformedness<NPWF>(
296        self,
297        new_path_wellformedness: NPWF,
298    ) -> Query<'sg, 'storage, 'rslv, LABEL, DATA, CMPL, NPWF, DWF, LO, DEq>
299    where
300        NPWF: for<'a> RegexMatcher<&'a LABEL> + 'rslv,
301    {
302        Query {
303            _phantom: PhantomData,
304            scope_graph: self.scope_graph,
305            path_wellformedness: new_path_wellformedness,
306            data_wellformedness: self.data_wellformedness,
307            label_order: self.label_order,
308            data_equivalence: self.data_equivalence,
309        }
310    }
311
312    pub fn with_data_wellformedness<NDWF>(
313        self,
314        new_data_wellformedness: NDWF,
315    ) -> Query<'sg, 'storage, 'rslv, LABEL, DATA, CMPL, PWF, NDWF, LO, DEq>
316    where
317        NDWF: DataWellformedness<DATA> + 'rslv,
318    {
319        Query {
320            _phantom: PhantomData,
321            scope_graph: self.scope_graph,
322            path_wellformedness: self.path_wellformedness,
323            data_wellformedness: new_data_wellformedness,
324            label_order: self.label_order,
325            data_equivalence: self.data_equivalence,
326        }
327    }
328
329    pub fn with_label_order<NLO>(
330        self,
331        new_label_order: NLO,
332    ) -> Query<'sg, 'storage, 'rslv, LABEL, DATA, CMPL, PWF, DWF, NLO, DEq>
333    where
334        NLO: LabelOrder<LABEL> + 'rslv,
335    {
336        Query {
337            _phantom: PhantomData,
338            scope_graph: self.scope_graph,
339            path_wellformedness: self.path_wellformedness,
340            data_wellformedness: self.data_wellformedness,
341            label_order: new_label_order,
342            data_equivalence: self.data_equivalence,
343        }
344    }
345
346    pub fn with_data_equivalence<NDEq>(
347        self,
348        new_data_equivalence: NDEq,
349    ) -> Query<'sg, 'storage, 'rslv, LABEL, DATA, CMPL, PWF, DWF, LO, NDEq>
350    where
351        NDEq: DataEquiv<DATA> + 'rslv,
352    {
353        Query {
354            _phantom: PhantomData,
355            scope_graph: self.scope_graph,
356            path_wellformedness: self.path_wellformedness,
357            data_wellformedness: self.data_wellformedness,
358            label_order: self.label_order,
359            data_equivalence: new_data_equivalence,
360        }
361    }
362}
363
364impl<'storage, LABEL, DATA, CMPL> ScopeGraph<'storage, LABEL, DATA, CMPL> {
365    pub fn query<'sg>(
366        &'sg self,
367    ) -> Query<
368        'storage,
369        'sg,
370        '_,
371        LABEL,
372        DATA,
373        CMPL,
374        (),
375        DefaultDataWellformedness,
376        DefaultLabelOrder,
377        DefaultDataEquiv,
378    >
379    where
380        'storage: 'sg,
381    {
382        Query {
383            _phantom: PhantomData,
384            scope_graph: self,
385            path_wellformedness: (),
386            data_wellformedness: DefaultDataWellformedness::default(),
387            label_order: DefaultLabelOrder::default(),
388            data_equivalence: DefaultDataEquiv::default(),
389        }
390    }
391}
scopegraphs_lib/resolve/mod.rs

scopegraphs_lib/resolve/
mod.rs
