catlog/tt/util/
dtry.rs

1//! Directories.
2
3use crate::{
4    tt::prelude::*,
5    zero::{LabelSegment, QualifiedLabel, QualifiedName},
6};
7
8/// An entry in a [Dtry].
9///
10/// We use naming conventions from UNIX directories to name the variants of this
11/// enum.
12#[derive(Clone)]
13pub enum DtryEntry<T> {
14    /// A leaf node.
15    File(T),
16    /// An internal node.
17    SubDir(Dtry<T>),
18}
19
20impl<T> DtryEntry<T> {
21    /// Produce a new directory given by mapping `f` over all of the
22    /// [DtryEntry::File] nodes.
23    pub fn map<S>(&self, f: &impl Fn(&T) -> S) -> DtryEntry<S> {
24        match self {
25            DtryEntry::File(x) => DtryEntry::File(f(x)),
26            DtryEntry::SubDir(d) => DtryEntry::SubDir(d.map(f)),
27        }
28    }
29
30    fn singleton(path: &[(FieldName, LabelSegment)], val: T) -> Self {
31        if path.is_empty() {
32            DtryEntry::File(val)
33        } else {
34            DtryEntry::SubDir(Dtry::singleton(path, val))
35        }
36    }
37}
38
39impl<T: Clone> DtryEntry<T> {
40    fn flatten_into(
41        &self,
42        namespace: QualifiedName,
43        label_namespace: QualifiedLabel,
44        out: &mut Vec<(QualifiedName, QualifiedLabel, T)>,
45    ) {
46        match self {
47            DtryEntry::File(x) => out.push((namespace, label_namespace, x.clone())),
48            DtryEntry::SubDir(d) => d.flatten_into(namespace, label_namespace, out),
49        }
50    }
51}
52
53/// A directory.
54///
55/// A `Dtry<T>` consists of a mapping from `FieldName`s to directory
56/// entries, where a directory entry is either a "File" ([DtryEntry::File]),
57/// that is an element of `T`, or a "subdirectory" ([DtryEntry::SubDir]),
58/// which is just another directory.
59///
60/// The terminology is slightly different from [the directories paper][1];
61/// in the directories paper we call [DtryEntry] a directory, and [Dtry] is
62/// just the internal node case of [DtryEntry] (internal node as opposed to
63/// leaf node). This makes `Dtry` no longer a monad (there isn't a unit),
64/// but it's slightly more convenient for our use case here (keeping track
65/// of specializations).
66///
67/// [1]: https://arxiv.org/abs/2504.19389
68#[derive(Clone)]
69pub struct Dtry<T>(Row<DtryEntry<T>>);
70
71impl<T> Dtry<T> {
72    /// Produce a new directory given by mapping `f` over all of the
73    /// [DtryEntry::File] nodes.
74    pub fn map<S>(&self, f: &impl Fn(&T) -> S) -> Dtry<S> {
75        Dtry(self.0.iter().map(|(name, (label, e))| (*name, (*label, e.map(f)))).collect())
76    }
77
78    /// Constructor for the empty directory.
79    pub fn empty() -> Dtry<T> {
80        Dtry(Row::empty())
81    }
82
83    /// Returns whether the directory is empty
84    pub fn is_empty(&self) -> bool {
85        self.0.is_empty()
86    }
87
88    /// Iterate through the entries of the directory
89    pub fn entries(&self) -> impl Iterator<Item = (&FieldName, &(LabelSegment, DtryEntry<T>))> {
90        self.0.iter()
91    }
92
93    /// Get the entry for `field` if it exists
94    pub fn entry(&self, field: &FieldName) -> Option<&DtryEntry<T>> {
95        self.0.get(*field)
96    }
97
98    /// Create a singleton directory with just one entry at the given path
99    pub fn singleton(path: &[(FieldName, LabelSegment)], val: T) -> Self {
100        assert!(!path.is_empty());
101        let ((field, label), path) = (path[0], &path[1..]);
102        Dtry([(field, (label, DtryEntry::singleton(path, val)))].into_iter().collect())
103    }
104}
105
106impl<T: Clone> Dtry<T> {
107    /// Produce the list of paths in `self` that refer to files, along with the
108    /// value of the files that they refer to
109    pub fn flatten(&self) -> Vec<(QualifiedName, QualifiedLabel, T)> {
110        let mut out = Vec::new();
111        self.flatten_into(vec![].into(), vec![].into(), &mut out);
112        out
113    }
114
115    fn flatten_into(
116        &self,
117        namespace: QualifiedName,
118        label_namespace: QualifiedLabel,
119        out: &mut Vec<(QualifiedName, QualifiedLabel, T)>,
120    ) {
121        for (field, (label, entry)) in self.entries() {
122            entry.flatten_into(namespace.snoc(*field), label_namespace.snoc(*label), out)
123        }
124    }
125}
126
127impl<T> From<IndexMap<FieldName, (LabelSegment, DtryEntry<T>)>> for Dtry<T> {
128    fn from(value: IndexMap<FieldName, (LabelSegment, DtryEntry<T>)>) -> Self {
129        Self(value.into())
130    }
131}
catlog/tt/util/dtry.rs

catlog/tt/util/
dtry.rs
