triblespace_core/
id.rs

1//! Identifier utilities and ownership mechanisms for Trible Space.
2//!
3//! For a deeper discussion see the [Identifiers](../book/src/deep-dive/identifiers.md) chapter of the Tribles Book.
4
5pub mod fucid;
6pub mod rngid;
7pub mod ufoid;
8
9use std::borrow::Borrow;
10use std::cell::RefCell;
11use std::convert::TryInto;
12use std::fmt::Display;
13use std::fmt::LowerHex;
14use std::fmt::UpperHex;
15use std::hash::Hash;
16use std::marker::PhantomData;
17use std::mem;
18use std::num::NonZero;
19use std::ops::Deref;
20
21use hex::FromHex;
22
23pub use fucid::fucid;
24pub use fucid::FUCIDsource;
25pub use rngid::rngid as genid;
26pub use rngid::rngid;
27pub use ufoid::ufoid;
28
29use crate::patch::Entry;
30use crate::patch::IdentitySchema;
31use crate::patch::PATCH;
32use crate::prelude::valueschemas::GenId;
33use crate::query::Constraint;
34use crate::query::ContainsConstraint;
35use crate::query::Variable;
36use crate::value::RawValue;
37use crate::value::VALUE_LEN;
38
39thread_local!(static OWNED_IDS: IdOwner = IdOwner::new());
40
41/// The length of a 128bit abstract identifier in bytes.
42pub const ID_LEN: usize = 16;
43
44/// Represents a 16 byte abstract identifier.
45pub type RawId = [u8; ID_LEN];
46
47/// Converts a 16 byte [RawId] reference into an 32 byte [RawValue].
48pub(crate) fn id_into_value(id: &RawId) -> RawValue {
49    let mut data = [0; VALUE_LEN];
50    data[16..32].copy_from_slice(id);
51    data
52}
53
54/// Converts a 32 byte [RawValue] reference into an 16 byte [RawId].
55/// Returns `None` if the value is not in the canonical ID format,
56/// i.e. the first 16 bytes are all zero.
57pub(crate) fn id_from_value(id: &RawValue) -> Option<RawId> {
58    if id[0..16] != [0; 16] {
59        return None;
60    }
61    let id = id[16..32].try_into().unwrap();
62    Some(id)
63}
64
65/// Represents a unique abstract 128 bit identifier.
66/// As we do not allow for all zero `nil` IDs,
67/// `Option<Id>` benefits from Option nieche optimizations.
68///
69/// Note that it has an alignment of 1, and can be referenced as a `[u8; 16]` [RawId].
70#[derive(Copy, Clone, Debug, PartialEq, Eq)]
71#[repr(C, packed(1))]
72pub struct Id {
73    inner: NonZero<u128>,
74}
75
76impl Id {
77    /// Creates a new `Id` from a [RawId] 16 byte array.
78    pub const fn new(id: RawId) -> Option<Self> {
79        unsafe { std::mem::transmute::<RawId, Option<Id>>(id) }
80    }
81
82    /// Parses a hexadecimal identifier string into an `Id`.
83    ///
84    /// Returns `None` if the input is not valid hexadecimal or represents the
85    /// nil identifier (all zero bytes).
86    pub fn from_hex(hex: &str) -> Option<Self> {
87        let raw = <RawId as FromHex>::from_hex(hex).ok()?;
88        Id::new(raw)
89    }
90
91    /// Forces the creation of an `Id` from a [RawId] without checking for nil.
92    ///
93    /// # Safety
94    ///
95    /// The caller must ensure that `id` is not the nil value of all zero bytes.
96    pub const unsafe fn force(id: RawId) -> Self {
97        std::mem::transmute::<RawId, Id>(id)
98    }
99
100    /// Transmutes a reference to a [RawId] into a reference to an `Id`.
101    /// Returns `None` if the referenced RawId is nil (all zero).
102    pub fn as_transmute_raw(id: &RawId) -> Option<&Self> {
103        if *id == [0; 16] {
104            None
105        } else {
106            Some(unsafe { std::mem::transmute::<&RawId, &Id>(id) })
107        }
108    }
109
110    /// Takes ownership of this Id from the current write context (i.e. thread).
111    /// Returns `None` if this Id was not found, because it is not associated with this
112    /// write context, or because it is currently aquired.
113    pub fn aquire(&self) -> Option<ExclusiveId> {
114        OWNED_IDS.with(|owner| owner.take(self))
115    }
116}
117
118impl PartialOrd for Id {
119    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
120        Some(self.cmp(other))
121    }
122}
123
124impl Ord for Id {
125    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
126        let s: &RawId = self;
127        let o: &RawId = other;
128        Ord::cmp(s, o)
129    }
130}
131
132impl Hash for Id {
133    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
134        let s: &RawId = self;
135        Hash::hash(s, state);
136    }
137}
138
139impl Deref for Id {
140    type Target = RawId;
141
142    fn deref(&self) -> &Self::Target {
143        unsafe { std::mem::transmute::<&Id, &RawId>(self) }
144    }
145}
146
147impl Borrow<RawId> for Id {
148    fn borrow(&self) -> &RawId {
149        self
150    }
151}
152
153impl AsRef<RawId> for Id {
154    fn as_ref(&self) -> &RawId {
155        self
156    }
157}
158
159impl AsRef<[u8]> for Id {
160    fn as_ref(&self) -> &[u8] {
161        &self[..]
162    }
163}
164
165impl From<Id> for RawId {
166    fn from(id: Id) -> Self {
167        *id
168    }
169}
170
171impl From<Id> for RawValue {
172    fn from(id: Id) -> Self {
173        let raw: RawId = id.into();
174        id_into_value(&raw)
175    }
176}
177
178impl Display for Id {
179    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
180        write!(f, "Id({self:X})")
181    }
182}
183
184impl LowerHex for Id {
185    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
186        for byte in &self[..] {
187            write!(f, "{byte:02x}")?;
188        }
189        Ok(())
190    }
191}
192
193impl UpperHex for Id {
194    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
195        for byte in &self[..] {
196            write!(f, "{byte:02X}")?;
197        }
198        Ok(())
199    }
200}
201
202impl From<Id> for uuid::Uuid {
203    fn from(id: Id) -> Self {
204        let id: &RawId = &id;
205        uuid::Uuid::from_slice(id).unwrap()
206    }
207}
208
209#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
210pub struct NilUuidError;
211
212impl TryFrom<uuid::Uuid> for Id {
213    type Error = NilUuidError;
214
215    fn try_from(id: uuid::Uuid) -> Result<Self, NilUuidError> {
216        let bytes = id.into_bytes();
217        Id::new(bytes).ok_or(NilUuidError)
218    }
219}
220
221impl std::fmt::Display for NilUuidError {
222    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
223        write!(
224            f,
225            "UUID conversion failed: the UUID is nil (all zero bytes)"
226        )
227    }
228}
229
230impl std::error::Error for NilUuidError {}
231
232#[doc(hidden)]
233pub use hex_literal::hex as _hex_literal_hex;
234
235/// Creates an `Id` from a hex string literal.
236///
237/// # Example
238/// ```
239/// use triblespace_core::id::id_hex;
240/// let id = id_hex!("7D06820D69947D76E7177E5DEA4EA773");
241/// ```
242#[macro_export]
243macro_rules! id_hex {
244    ( $data:expr ) => {
245        $crate::id::Id::new($crate::id::_hex_literal_hex!($data)).unwrap()
246    };
247}
248
249pub use id_hex;
250
251/// Represents an ID that can only be used by a single writer at a time.
252///
253/// `ExclusiveId`s are associated with one owning context (typically a thread) at a time.
254/// Because they are `Send` and `!Sync`, they can be passed between contexts, but not used concurrently.
255/// This makes use of Rust's borrow checker to enforce a weaker form of software transactional memory (STM) without rollbacks - as these are not an issue with the heavy use of copy-on-write data structures.
256///
257/// They are automatically associated with the thread they are dropped from, which can be used in queries via the [local_ids] constraint.
258/// You can also make use of explicit [IdOwner] containers to store them when not actively used in a transaction.
259///
260/// Most methods defined on [ExclusiveId] are low-level primitives meant to be used for the implementation of new ownership management strategies,
261/// such as a transactional database that tracks checked out IDs for ownership, or distributed ledgers like blockchains.
262///
263#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
264#[repr(transparent)]
265pub struct ExclusiveId {
266    pub id: Id,
267    // Make sure that the type can't be syntactically initialized.
268    // Also make sure that we don't get auto impl of Send and Sync
269    _private: PhantomData<*const ()>,
270}
271
272unsafe impl Send for ExclusiveId {}
273
274impl ExclusiveId {
275    /// Forces a regular (read-only) `Id` to become a writable `ExclusiveId`.
276    ///
277    /// This is a low-level primitive that is meant to be used for the implementation of new ownership management strategies,
278    /// such as a transactional database that tracks checked out IDs for ownership, or distributed ledgers like blockchains.
279    ///
280    /// This should be done with care, as it allows scenarios where multiple writers can create conflicting information for the same ID.
281    /// Similar caution should be applied when using the `force_ref` and `forget` methods.
282    ///
283    /// # Arguments
284    ///
285    /// * `id` - The `Id` to be forced into an `ExclusiveId`.
286    pub fn force(id: Id) -> Self {
287        Self {
288            id,
289            _private: PhantomData,
290        }
291    }
292
293    /// Safely transmutes a reference to an `Id` into a reference to an `ExclusiveId`.
294    ///
295    /// Similar caution should be applied when using the `force` method.
296    ///
297    /// # Arguments
298    ///
299    /// * `id` - A reference to the `Id` to be transmuted.
300    pub fn force_ref(id: &Id) -> &Self {
301        unsafe { std::mem::transmute(id) }
302    }
303
304    /// Releases the `ExclusiveId`, returning the underlying `Id`.
305    ///
306    /// # Returns
307    ///
308    /// The underlying `Id`.
309    pub fn release(self) -> Id {
310        let id = self.id;
311        mem::drop(self);
312        id
313    }
314
315    /// Forgets the `ExclusiveId`, leaking ownership of the underlying `Id`, while returning it.
316    ///
317    /// This is not as potentially problematic as [force](ExclusiveId::force), because it prevents further writes with the `ExclusiveId`, thus avoiding potential conflicts.
318    ///
319    /// # Returns
320    ///
321    /// The underlying `Id`.
322    pub fn forget(self) -> Id {
323        let id = self.id;
324        mem::forget(self);
325        id
326    }
327}
328
329impl Drop for ExclusiveId {
330    fn drop(&mut self) {
331        OWNED_IDS.with(|ids| {
332            ids.force_insert(self);
333        });
334    }
335}
336
337impl Deref for ExclusiveId {
338    type Target = Id;
339
340    fn deref(&self) -> &Self::Target {
341        &self.id
342    }
343}
344
345impl Borrow<RawId> for ExclusiveId {
346    fn borrow(&self) -> &RawId {
347        self
348    }
349}
350
351impl Borrow<Id> for ExclusiveId {
352    fn borrow(&self) -> &Id {
353        self
354    }
355}
356
357impl AsRef<Id> for ExclusiveId {
358    fn as_ref(&self) -> &Id {
359        self
360    }
361}
362
363impl AsRef<ExclusiveId> for ExclusiveId {
364    fn as_ref(&self) -> &ExclusiveId {
365        self
366    }
367}
368
369impl AsRef<RawId> for ExclusiveId {
370    fn as_ref(&self) -> &RawId {
371        self
372    }
373}
374
375impl AsRef<[u8]> for ExclusiveId {
376    fn as_ref(&self) -> &[u8] {
377        &self[..]
378    }
379}
380
381impl Display for ExclusiveId {
382    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
383        let id: &Id = self;
384        write!(f, "ExclusiveId({id:X})")
385    }
386}
387
388/// A constraint that checks if a variable is an `ExclusiveId` associated with the current write context (i.e. thread).
389pub fn local_ids(v: Variable<GenId>) -> impl Constraint<'static> {
390    OWNED_IDS.with(|owner| owner.has(v))
391}
392
393/// A container for [ExclusiveId]s, allowing for explicit ownership management.
394/// There is an implicit `IdOwner` for each thread, to which `ExclusiveId`s are associated when they are dropped,
395/// and which can be queried via the [local_ids] constraint.
396///
397/// # Example
398///
399/// ```
400/// use triblespace_core::id::{IdOwner, ExclusiveId, fucid};
401/// let mut owner = IdOwner::new();
402/// let exclusive_id = fucid();
403/// let id = owner.insert(exclusive_id);
404///
405/// assert!(owner.owns(&id));
406/// assert_eq!(owner.take(&id), Some(ExclusiveId::force(id)));
407/// assert!(!owner.owns(&id));
408/// ```
409///
410pub struct IdOwner {
411    owned_ids: RefCell<PATCH<ID_LEN, IdentitySchema, ()>>,
412}
413
414/// An `ExclusiveId` that is associated with an `IdOwner`.
415/// It is automatically returned to the `IdOwner` when dropped.
416pub struct OwnedId<'a> {
417    pub id: Id,
418    owner: &'a IdOwner,
419}
420
421impl Default for IdOwner {
422    fn default() -> Self {
423        Self::new()
424    }
425}
426
427impl IdOwner {
428    /// Creates a new `IdOwner`.
429    ///
430    /// This is typically not necessary, as each thread has an implicit `IdOwner` associated with it.
431    ///
432    /// # Returns
433    ///
434    /// A new `IdOwner`.
435    pub fn new() -> Self {
436        Self {
437            owned_ids: RefCell::new(PATCH::<ID_LEN, IdentitySchema, ()>::new()),
438        }
439    }
440
441    /// Inserts an `ExclusiveId` into the `IdOwner`, returning the underlying `Id`.
442    ///
443    /// # Arguments
444    ///
445    /// * `id` - The `ExclusiveId` to be inserted.
446    ///
447    /// # Returns
448    ///
449    /// The underlying `Id`.
450    pub fn insert(&mut self, id: ExclusiveId) -> Id {
451        self.force_insert(&id);
452        id.forget()
453    }
454
455    /// Defers inserting an `ExclusiveId` into the `IdOwner`, returning an `OwnedId`.
456    /// The `OwnedId` will return the `ExclusiveId` to the `IdOwner` when dropped.
457    /// This is useful if you generated an `ExclusiveId` that you want to use temporarily,
458    /// but want to make sure it is returned to the `IdOwner` when you are done.
459    ///
460    /// # Arguments
461    ///
462    /// * `id` - The `ExclusiveId` to be inserted.
463    ///
464    /// # Returns
465    ///
466    /// An `OwnedId` that will return the `ExclusiveId` to the `IdOwner` when dropped.
467    ///
468    /// # Example
469    ///
470    /// ```
471    /// use triblespace_core::prelude::*;
472    /// use valueschemas::ShortString;
473    /// use triblespace_core::id_hex;
474    ///
475    /// let mut owner = IdOwner::new();
476    /// let owned_id = owner.defer_insert(fucid());
477    /// let trible = Trible::new(&owned_id, &id_hex!("7830D7B3C2DCD44EB3FA68C93D06B973"), &ShortString::value_from("Hello, World!"));
478    /// ```
479    pub fn defer_insert(&self, id: ExclusiveId) -> OwnedId<'_> {
480        OwnedId {
481            id: id.forget(),
482            owner: self,
483        }
484    }
485
486    /// Forces an `Id` into the `IdOwner` as an `ExclusiveId`.
487    ///
488    /// # Arguments
489    ///
490    /// * `id` - The `Id` to be forced into an `ExclusiveId`.
491    pub fn force_insert(&self, id: &Id) {
492        let entry = Entry::new(id);
493        self.owned_ids.borrow_mut().insert(&entry);
494    }
495
496    /// Takes an `Id` from the `IdOwner`, returning it as an `ExclusiveId`.
497    ///
498    /// # Arguments
499    ///
500    /// * `id` - The `Id` to be taken.
501    ///
502    /// # Returns
503    ///
504    /// An `ExclusiveId` if the `Id` was found, otherwise `None`.
505    pub fn take(&self, id: &Id) -> Option<ExclusiveId> {
506        if self.owned_ids.borrow().has_prefix(id) {
507            self.owned_ids.borrow_mut().remove(id);
508            Some(ExclusiveId::force(*id))
509        } else {
510            None
511        }
512    }
513
514    /// Get an `OwnedId` from the `IdOwner`.
515    /// The `OwnedId` will return the `ExclusiveId` to the `IdOwner` when dropped.
516    /// This is useful for temporary exclusive access to an `Id`.
517    /// If you want to keep the `Id` for longer, you can use the `take` method,
518    /// but you will have to manually return it to the `IdOwner` when you are done.
519    ///
520    /// # Arguments
521    ///
522    /// * `id` - The `Id` to be taken.
523    ///
524    /// # Returns
525    ///
526    /// An `OwnedId` if the `Id` was found, otherwise `None`.
527    ///
528    /// # Example
529    ///
530    /// ```
531    /// use triblespace_core::id::{IdOwner, ExclusiveId, fucid};
532    /// let mut owner = IdOwner::new();
533    /// let exclusive_id = fucid();
534    /// let id = owner.insert(exclusive_id);
535    ///  {
536    ///     let mut owned_id = owner.borrow(&id).unwrap();
537    ///
538    ///     assert_eq!(owned_id.id, id);
539    ///     assert!(!owner.owns(&id));
540    ///  }
541    /// assert!(owner.owns(&id));
542    /// ```
543    pub fn borrow<'a>(&'a self, id: &Id) -> Option<OwnedId<'a>> {
544        self.take(id).map(move |id| OwnedId {
545            id: id.forget(),
546            owner: self,
547        })
548    }
549
550    /// Checks if the `IdOwner` owns an `Id`.
551    ///
552    /// # Arguments
553    ///
554    /// * `id` - The `Id` to be checked.
555    ///
556    /// # Returns
557    ///
558    /// `true` if the `Id` is owned by the `IdOwner`, otherwise `false`.
559    pub fn owns(&self, id: &Id) -> bool {
560        self.owned_ids.borrow().has_prefix(id)
561    }
562}
563
564impl Deref for OwnedId<'_> {
565    type Target = ExclusiveId;
566
567    fn deref(&self) -> &Self::Target {
568        ExclusiveId::force_ref(&self.id)
569    }
570}
571
572impl Borrow<RawId> for OwnedId<'_> {
573    fn borrow(&self) -> &RawId {
574        self
575    }
576}
577
578impl Borrow<Id> for OwnedId<'_> {
579    fn borrow(&self) -> &Id {
580        self
581    }
582}
583
584impl Borrow<ExclusiveId> for OwnedId<'_> {
585    fn borrow(&self) -> &ExclusiveId {
586        self
587    }
588}
589
590impl AsRef<ExclusiveId> for OwnedId<'_> {
591    fn as_ref(&self) -> &ExclusiveId {
592        self
593    }
594}
595
596impl AsRef<Id> for OwnedId<'_> {
597    fn as_ref(&self) -> &Id {
598        self
599    }
600}
601
602impl AsRef<RawId> for OwnedId<'_> {
603    fn as_ref(&self) -> &RawId {
604        self
605    }
606}
607
608impl AsRef<[u8]> for OwnedId<'_> {
609    fn as_ref(&self) -> &[u8] {
610        &self[..]
611    }
612}
613
614impl Display for OwnedId<'_> {
615    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
616        let id: &Id = self;
617        write!(f, "OwnedId({id:X})")
618    }
619}
620
621impl<'a> Drop for OwnedId<'a> {
622    fn drop(&mut self) {
623        self.owner.force_insert(&(self.id));
624    }
625}
626
627impl ContainsConstraint<'static, GenId> for &IdOwner {
628    type Constraint =
629        <PATCH<ID_LEN, IdentitySchema, ()> as ContainsConstraint<'static, GenId>>::Constraint;
630
631    fn has(self, v: Variable<GenId>) -> Self::Constraint {
632        self.owned_ids.borrow().clone().has(v)
633    }
634}
635
636#[cfg(test)]
637mod tests {
638    use crate::examples::literature;
639    use crate::id::ExclusiveId;
640    use crate::prelude::*;
641    use crate::query::Query;
642    use crate::query::VariableContext;
643    use crate::value::schemas::genid::GenId;
644    use crate::value::schemas::shortstring::ShortString;
645
646    #[test]
647    fn id_formatting() {
648        let id: Id = id_hex!("7D06820D69947D76E7177E5DEA4EA773");
649        assert_eq!(format!("{id:x}"), "7d06820d69947d76e7177e5dea4ea773");
650        assert_eq!(format!("{id:X}"), "7D06820D69947D76E7177E5DEA4EA773");
651    }
652
653    #[test]
654    fn ns_local_ids() {
655        let mut kb = TribleSet::new();
656
657        {
658            let isaac = ufoid();
659            let jules = ufoid();
660            kb += entity! { &jules @
661               literature::firstname: "Jules",
662               literature::lastname: "Verne"
663            };
664            kb += entity! { &isaac @
665               literature::firstname: "Isaac",
666               literature::lastname: "Asimov"
667            };
668        }
669
670        let mut r: Vec<_> = find!(
671            (author: ExclusiveId, name: String),
672            and!(
673                local_ids(author),
674                pattern!(&kb, [
675                    {?author @
676                        literature::firstname: ?name
677                    }])
678            )
679        )
680        .map(|(_, n)| n)
681        .collect();
682        r.sort();
683
684        assert_eq!(vec!["Isaac", "Jules"], r);
685    }
686
687    #[test]
688    fn ns_local_ids_bad_estimates_panics() {
689        let mut kb = TribleSet::new();
690
691        {
692            let isaac = ufoid();
693            let jules = ufoid();
694            kb += entity! { &jules @
695               literature::firstname: "Jules",
696               literature::lastname: "Verne"
697            };
698            kb += entity! { &isaac @
699               literature::firstname: "Isaac",
700               literature::lastname: "Asimov"
701            };
702        }
703
704        let mut ctx = VariableContext::new();
705        macro_rules! __local_find_context {
706            () => {
707                &mut ctx
708            };
709        }
710        let author = ctx.next_variable::<GenId>();
711        let name = ctx.next_variable::<ShortString>();
712
713        let base = and!(
714            local_ids(author),
715            pattern!(&kb, [{ ?author @ literature::firstname: ?name }])
716        );
717
718        let mut wrapper = crate::debug::query::EstimateOverrideConstraint::new(base);
719        wrapper.set_estimate(author.index, 100);
720        wrapper.set_estimate(name.index, 1);
721
722        let q: Query<_, _, _> =
723            Query::new(wrapper, |binding| String::from_value(name.extract(binding)));
724        let r: Vec<_> = q.collect();
725        assert_eq!(r, vec!["Isaac", "Jules"]);
726    }
727}
triblespace_core/id.rs

triblespace_core/
id.rs
