catlog/zero/
qualified.rs

1/*! Qualified names and labels.
2
3TODO
4 */
5
6use std::fmt::Display;
7use std::{collections::HashMap, hash::Hash};
8
9use derive_more::From;
10use itertools::Itertools;
11use ustr::Ustr;
12use uuid::Uuid;
13
14#[cfg(feature = "serde")]
15use serde::{self, Deserialize, Serialize};
16#[cfg(feature = "serde-wasm")]
17use tsify::Tsify;
18
19use super::column::{Column, IndexedHashColumn, Mapping, MutMapping};
20
21/** A segment in a [qualified name](QualifiedName).
22
23A segment is either a meaningless, machine-generated identifier, represented as
24a [UUID](Uuid), or a meaningful, operator-generated name, represented as an
25interned string.
26 */
27#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, From)]
28pub enum NameSegment {
29    /// A universally unique identifier (UUID).
30    Uuid(Uuid),
31
32    /// A human-readable name, assumed unique within the relevant context.
33    Text(Ustr),
34}
35
36impl From<&str> for NameSegment {
37    fn from(name: &str) -> Self {
38        Self::Text(name.into())
39    }
40}
41
42impl Display for NameSegment {
43    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
44        match self {
45            Self::Uuid(uiid) => uiid.as_braced().fmt(f),
46            Self::Text(name) => name.fmt(f),
47        }
48    }
49}
50
51impl NameSegment {
52    /// Serializes the segment into a string.
53    pub fn serialize_string(&self) -> String {
54        match self {
55            Self::Uuid(uiid) => uiid.to_string(),
56            Self::Text(name) => format!("`{name}`"),
57        }
58    }
59
60    /// Deserializes a segment from a string.
61    pub fn deserialize_str(input: &str) -> Result<Self, String> {
62        let mut chars = input.chars();
63        if chars.next() == Some('`') && chars.next_back() == Some('`') {
64            Ok(Self::Text(chars.as_str().into()))
65        } else {
66            let uuid = Uuid::parse_str(input).map_err(|err| format!("Invalid UUID: {err}"))?;
67            Ok(Self::Uuid(uuid))
68        }
69    }
70}
71
72/** A qualified name, consisting of a sequence of [name segments](NameSegment).
73
74A qualified name is a sequence of segments that unambiguously names an element
75in a set, or a family of sets, or a family of family of sets, and so on. For
76example, a qualified name with three segments can be constructed as
77
78```
79# use catlog::zero::qualified::*;
80let name: QualifiedName = ["foo", "bar", "baz"].map(NameSegment::from).into();
81assert_eq!(name.to_string(), "foo.bar.baz");
82```
83
84# Data structure
85
86At this time, a qualified name is stored simply as a vector of name segments.
87Various optimizations could be considered, such as an `Rc<[NameSegment]>` or,
88since qualified names tend to have only a few segments, a
89`SmallVec<[NameSegment; n]>` for some choice of `n`. These will be considered
90premature optimizations until there is good evidence in favor of them.
91
92# Serialization
93
94To simplify their use in JavaScript, qualified name are serialized as flat
95strings with segments separated by periods. Human-readable names are quoted with
96backticks regardless of whether they contain whitespace, which makes parsing
97easier. Note that the [display](Display) format is different from the
98serialization format.
99 */
100#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, From)]
101#[cfg_attr(feature = "serde-wasm", derive(Tsify))]
102#[cfg_attr(feature = "serde-wasm", tsify(into_wasm_abi, from_wasm_abi))]
103pub struct QualifiedName(
104    #[cfg_attr(feature = "serde-wasm", tsify(type = "string"))] Vec<NameSegment>,
105);
106
107/// Helper function to construct a qualified name.
108pub fn name(x: impl Into<QualifiedName>) -> QualifiedName {
109    x.into()
110}
111
112impl<const N: usize> From<[NameSegment; N]> for QualifiedName {
113    fn from(segments: [NameSegment; N]) -> Self {
114        Vec::from(segments).into()
115    }
116}
117
118impl<const N: usize> From<[Uuid; N]> for QualifiedName {
119    fn from(segments: [Uuid; N]) -> Self {
120        segments.map(NameSegment::Uuid).into()
121    }
122}
123
124impl<const N: usize> From<[&str; N]> for QualifiedName {
125    fn from(segments: [&str; N]) -> Self {
126        segments.map(NameSegment::from).into()
127    }
128}
129
130impl From<Uuid> for QualifiedName {
131    fn from(id: Uuid) -> Self {
132        Self::single(id.into())
133    }
134}
135
136impl From<Ustr> for QualifiedName {
137    fn from(name: Ustr) -> Self {
138        Self::single(name.into())
139    }
140}
141
142impl From<&str> for QualifiedName {
143    fn from(name: &str) -> Self {
144        Self::single(name.into())
145    }
146}
147
148impl Display for QualifiedName {
149    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
150        fmt_qualified(
151            f,
152            &self.0,
153            |segment| matches!(segment, NameSegment::Text(name) if name.contains(char::is_whitespace)),
154        )
155    }
156}
157
158fn fmt_qualified<T: Display>(
159    f: &mut std::fmt::Formatter<'_>,
160    segments: &[T],
161    mut show_quotes: impl FnMut(&T) -> bool,
162) -> std::fmt::Result {
163    let n = segments.len();
164    for (i, segment) in segments.iter().enumerate() {
165        if i > 0 {
166            write!(f, ".")?;
167        }
168        let quote = n > 1 && show_quotes(segment);
169        if quote {
170            write!(f, "`")?;
171        }
172        write!(f, "{segment}")?;
173        if quote {
174            write!(f, "`")?;
175        }
176    }
177    Ok(())
178}
179
180#[cfg(feature = "serde")]
181impl Serialize for QualifiedName {
182    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
183    where
184        S: serde::Serializer,
185    {
186        serializer.serialize_str(self.serialize_string().as_str())
187    }
188}
189
190#[cfg(feature = "serde")]
191impl<'de> Deserialize<'de> for QualifiedName {
192    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
193    where
194        D: serde::Deserializer<'de>,
195    {
196        deserializer.deserialize_str(QualifiedNameVisitor)
197    }
198}
199
200#[cfg(feature = "serde")]
201struct QualifiedNameVisitor;
202
203#[cfg(feature = "serde")]
204impl<'de> serde::de::Visitor<'de> for QualifiedNameVisitor {
205    type Value = QualifiedName;
206
207    fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
208        write!(formatter, "a qualified name as a dot-separated string")
209    }
210
211    fn visit_str<E>(self, input: &str) -> Result<Self::Value, E>
212    where
213        E: serde::de::Error,
214    {
215        QualifiedName::deserialize_str(input).map_err(E::custom)
216    }
217}
218
219impl QualifiedName {
220    /// Constructs a qualified name with a single segment.
221    pub fn single(segment: NameSegment) -> Self {
222        Self(vec![segment])
223    }
224
225    /// Iterates over the segments of the qualified name.
226    pub fn segments(&self) -> impl Iterator<Item = &NameSegment> {
227        self.0.iter()
228    }
229
230    /// Gets the segment from a qualified name with only one segment.
231    pub fn only(&self) -> Option<NameSegment> {
232        if self.0.len() == 1 {
233            Some(self.0[0])
234        } else {
235            None
236        }
237    }
238
239    /// Serializes the qualified name into a string.
240    pub fn serialize_string(&self) -> String {
241        self.segments().map(|segment| segment.serialize_string()).join(".")
242    }
243
244    /// Deserializes a qualified name from a string.
245    pub fn deserialize_str(input: &str) -> Result<Self, String> {
246        let segments: Result<Vec<_>, _> =
247            input.split(".").map(NameSegment::deserialize_str).collect();
248        Ok(segments?.into())
249    }
250}
251
252/// A segment in a [qualified label](QualifiedLabel).
253#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, From)]
254#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
255#[cfg_attr(feature = "serde", serde(untagged))]
256#[cfg_attr(feature = "serde-wasm", derive(Tsify))]
257#[cfg_attr(feature = "serde-wasm", tsify(into_wasm_abi, from_wasm_abi))]
258pub enum LabelSegment {
259    /// Textual label for a named entity.
260    Text(Ustr),
261
262    /// Integer index representing an anonymous entity.
263    Index(usize),
264}
265
266impl From<&str> for LabelSegment {
267    fn from(label: &str) -> Self {
268        Self::Text(label.into())
269    }
270}
271
272impl Display for LabelSegment {
273    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
274        match self {
275            Self::Text(label) => label.fmt(f),
276            Self::Index(index) => index.fmt(f),
277        }
278    }
279}
280
281/// A qualified label, consisting of a sequence of [label segments](LabelSegment).
282#[derive(Clone, Debug, PartialEq, Eq, From)]
283#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
284#[cfg_attr(feature = "serde-wasm", derive(Tsify))]
285#[cfg_attr(feature = "serde-wasm", tsify(into_wasm_abi, from_wasm_abi))]
286pub struct QualifiedLabel(Vec<LabelSegment>);
287
288/// Helper function to construct a qualified label.
289pub fn label(x: impl Into<QualifiedLabel>) -> QualifiedLabel {
290    x.into()
291}
292
293impl<const N: usize> From<[LabelSegment; N]> for QualifiedLabel {
294    fn from(segments: [LabelSegment; N]) -> Self {
295        Vec::from(segments).into()
296    }
297}
298
299impl<const N: usize> From<[&str; N]> for QualifiedLabel {
300    fn from(segments: [&str; N]) -> Self {
301        segments.map(LabelSegment::from).into()
302    }
303}
304
305impl From<Ustr> for QualifiedLabel {
306    fn from(label: Ustr) -> Self {
307        Self::single(label.into())
308    }
309}
310
311impl From<&str> for QualifiedLabel {
312    fn from(label: &str) -> Self {
313        Self::single(label.into())
314    }
315}
316
317impl From<usize> for QualifiedLabel {
318    fn from(value: usize) -> Self {
319        Self::single(value.into())
320    }
321}
322
323impl Display for QualifiedLabel {
324    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
325        fmt_qualified(
326            f,
327            &self.0,
328            |segment| matches!(segment, LabelSegment::Text(label) if label.contains(char::is_whitespace)),
329        )
330    }
331}
332
333impl QualifiedLabel {
334    /// Constructs a qualified label with a single segment.
335    pub fn single(segment: LabelSegment) -> Self {
336        Self(vec![segment])
337    }
338
339    /// Iterates over the segments of the qualified label.
340    pub fn segments(&self) -> impl Iterator<Item = &LabelSegment> {
341        self.0.iter()
342    }
343}
344
345/// A namespace in which to resolve qualified labels as qualified names.
346#[derive(Clone, Debug)]
347pub struct Namespace {
348    inner: HashMap<NameSegment, Namespace>,
349    uuid_labels: Option<IndexedHashColumn<Uuid, LabelSegment>>,
350}
351
352/// The result of looking up a qualified name by qualified label.
353#[derive(Clone, Debug, PartialEq, Eq)]
354#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
355#[cfg_attr(feature = "serde", serde(tag = "tag", content = "content"))]
356#[cfg_attr(feature = "serde-wasm", derive(Tsify))]
357#[cfg_attr(feature = "serde-wasm", tsify(into_wasm_abi, from_wasm_abi))]
358pub enum NameLookup {
359    /// A unique name with the given label exists.
360    Unique(QualifiedName),
361
362    /// Multiple names with the given label exist, with arbitrary one returned.
363    Arbitrary(QualifiedName),
364
365    /// No name with the given label exists.
366    None,
367}
368
369impl Namespace {
370    /// Creates an empty namespace for text segments.
371    pub fn new_for_text() -> Self {
372        Self {
373            inner: Default::default(),
374            uuid_labels: None,
375        }
376    }
377
378    /// Creates an empty namespace for UUID segments.
379    pub fn new_for_uuid() -> Self {
380        Self {
381            inner: Default::default(),
382            uuid_labels: Some(Default::default()),
383        }
384    }
385
386    /// Adds a new inner namespace.
387    pub fn add_inner(&mut self, name: NameSegment, inner: Self) {
388        assert!(
389            self.inner.insert(name, inner).is_none(),
390            "Inner namespace already exists for segment: {name}"
391        );
392    }
393
394    /// Sets the label segment associated with a UUID.
395    pub fn set_label(&mut self, uuid: Uuid, label: LabelSegment) {
396        self.uuid_labels.as_mut().expect("Should be a UUID namespace").set(uuid, label);
397    }
398
399    /// Tries to get a human-readable label for a name.
400    pub fn label(&self, name: &QualifiedName) -> Option<QualifiedLabel> {
401        let mut namespace = Some(self);
402        let labels: Option<Vec<_>> = name
403            .segments()
404            .map(|segment| {
405                let maybe_label = match segment {
406                    NameSegment::Uuid(uuid) => namespace
407                        .and_then(|ns| ns.uuid_labels.as_ref())
408                        .and_then(|ul| ul.apply_to_ref(uuid)),
409                    NameSegment::Text(name) => Some(LabelSegment::Text(*name)),
410                };
411                namespace = namespace.and_then(|ns| ns.inner.get(segment));
412                maybe_label
413            })
414            .collect();
415        Some(labels?.into())
416    }
417
418    /// Tries to get a name corresponding to a label.
419    pub fn name_with_label(&self, label: &QualifiedLabel) -> NameLookup {
420        let mut namespace = Some(self);
421        let mut ambiguous = false;
422        let names: Option<Vec<_>> = label
423            .segments()
424            .map(|segment| {
425                let maybe_uuid_labels = namespace.and_then(|ns| ns.uuid_labels.as_ref());
426                let maybe_name = match (maybe_uuid_labels, segment) {
427                    (Some(uuid_labels), _) => {
428                        let mut uuids = uuid_labels.preimage(segment);
429                        let maybe_uuid = uuids.next();
430                        if uuids.next().is_some() {
431                            ambiguous = true;
432                        }
433                        maybe_uuid.map(NameSegment::Uuid)
434                    }
435                    (None, LabelSegment::Text(text)) => Some(NameSegment::Text(*text)),
436                    (None, LabelSegment::Index(_)) => None,
437                };
438                namespace = namespace
439                    .and_then(|ns| maybe_name.as_ref().and_then(|name| ns.inner.get(name)));
440                maybe_name
441            })
442            .collect();
443        match names {
444            Some(names) if !ambiguous => NameLookup::Unique(names.into()),
445            Some(names) => NameLookup::Arbitrary(names.into()),
446            None => NameLookup::None,
447        }
448    }
449}
450
451#[cfg(test)]
452mod tests {
453    use super::*;
454    use uuid::uuid;
455
456    const UUID1: Uuid = uuid!("67e55044-10b1-426f-9247-bb680e5fe0c8");
457    const UUID2: Uuid = uuid!("f81d4fae-7dec-11d0-a765-00a0c91e6bf6");
458
459    #[test]
460    fn display_name() {
461        let string = name(UUID1).to_string();
462        assert_eq!(string.chars().next_tuple(), Some(('{', '6', '7', 'e')));
463        assert_eq!(string.chars().next_back(), Some('}'));
464
465        assert_eq!(name("foo").to_string(), "foo");
466        assert_eq!(name("foo bar").to_string(), "foo bar");
467        assert_eq!(name(["foo bar", "baz"]).to_string(), "`foo bar`.baz");
468    }
469
470    #[test]
471    fn serialize_name() {
472        let qual_name = name(UUID1);
473        let serialized = qual_name.serialize_string();
474        assert_eq!(serialized.chars().next_tuple(), Some(('6', '7', 'e')));
475        assert_eq!(QualifiedName::deserialize_str(&serialized), Ok(qual_name));
476
477        let qual_name = name(["foo", "bar", "baz"].map(NameSegment::from));
478        let serialized = qual_name.serialize_string();
479        assert_eq!(serialized, "`foo`.`bar`.`baz`");
480        assert_eq!(QualifiedName::deserialize_str(&serialized), Ok(qual_name));
481    }
482
483    #[test]
484    fn display_label() {
485        assert_eq!(label("foo").to_string(), "foo");
486        assert_eq!(label("foo bar").to_string(), "foo bar");
487        assert_eq!(label(2).to_string(), "2");
488
489        assert_eq!(label([LabelSegment::from("foo"), LabelSegment::from(1)]).to_string(), "foo.1");
490        assert_eq!(label(["foo bar", "baz"]).to_string(), "`foo bar`.baz");
491    }
492
493    #[test]
494    fn namespaces() {
495        let mut child = Namespace::new_for_uuid();
496        child.set_label(UUID1, "bar".into());
497        child.set_label(UUID2, "baz".into());
498        let mut root = Namespace::new_for_uuid();
499        root.add_inner(UUID1.into(), child);
500        root.add_inner(UUID2.into(), Namespace::new_for_text());
501        root.set_label(UUID1, "foo".into());
502        root.set_label(UUID2, "textual".into());
503
504        let (qual_name, qual_label) = (name([UUID1, UUID2]), label(["foo", "baz"]));
505        assert_eq!(root.label(&qual_name), Some(qual_label.clone()));
506        assert_eq!(root.name_with_label(&qual_label), NameLookup::Unique(qual_name));
507
508        let qual_name =
509            name([NameSegment::Uuid(UUID1), NameSegment::Uuid(UUID1), NameSegment::from("biz")]);
510        let qual_label = label(["foo", "bar", "biz"]);
511        assert_eq!(root.label(&qual_name), Some(qual_label.clone()));
512        assert_eq!(root.name_with_label(&qual_label), NameLookup::Unique(qual_name));
513
514        assert_eq!(root.label(&name([UUID2, UUID1])), None);
515        assert_eq!(root.name_with_label(&label(["bar", "foo"])), NameLookup::None);
516
517        let mut ambiguous = Namespace::new_for_uuid();
518        ambiguous.set_label(UUID1, "foo".into());
519        ambiguous.set_label(UUID2, "foo".into());
520        assert!(matches!(ambiguous.name_with_label(&label("foo")), NameLookup::Arbitrary(_)));
521    }
522}
catlog/zero/qualified.rs

catlog/zero/
qualified.rs
