catlog/zero/
qualified.rs

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

catlog/zero/
qualified.rs
