re_log_types/path/
entity_path.rs

1use std::sync::Arc;
2
3use ahash::{HashMap, HashSet};
4use itertools::Itertools as _;
5
6use re_byte_size::SizeBytes;
7use re_string_interner::InternedString;
8
9use crate::{EntityPathPart, hash::Hash64};
10
11// ----------------------------------------------------------------------------
12
13/// A 64 bit hash of [`EntityPath`] with very small risk of collision.
14#[derive(Copy, Clone, Eq, PartialOrd, Ord)]
15pub struct EntityPathHash(Hash64);
16
17impl re_byte_size::SizeBytes for EntityPathHash {
18    #[inline]
19    fn heap_size_bytes(&self) -> u64 {
20        self.0.heap_size_bytes()
21    }
22}
23
24impl EntityPathHash {
25    /// Sometimes used as the hash of `None`.
26    pub const NONE: Self = Self(Hash64::ZERO);
27
28    /// From an existing u64. Use this only for data conversions.
29    #[inline]
30    pub fn from_u64(i: u64) -> Self {
31        Self(Hash64::from_u64(i))
32    }
33
34    #[inline]
35    pub fn hash64(&self) -> u64 {
36        self.0.hash64()
37    }
38
39    #[inline]
40    pub fn is_some(&self) -> bool {
41        *self != Self::NONE
42    }
43
44    #[inline]
45    pub fn is_none(&self) -> bool {
46        *self == Self::NONE
47    }
48}
49
50impl std::hash::Hash for EntityPathHash {
51    #[inline]
52    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
53        self.0.hash(state);
54    }
55}
56
57impl std::cmp::PartialEq for EntityPathHash {
58    #[inline]
59    fn eq(&self, other: &Self) -> bool {
60        self.0.eq(&other.0)
61    }
62}
63
64impl nohash_hasher::IsEnabled for EntityPathHash {}
65
66impl std::fmt::Debug for EntityPathHash {
67    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
68        write!(f, "EntityPathHash({:016X})", self.hash64())
69    }
70}
71
72// ----------------------------------------------------------------------------
73
74/// The unique identifier of an entity, e.g. `camera/3/points`
75///
76/// The entity path is a list of [parts][EntityPathPart] separated by slashes.
77/// Each part is a non-empty string, that can contain any character.
78/// When written as a string, some characters in the parts need to be escaped with a `\`
79/// (only character, numbers, `.`, `-`, `_` does not need escaping).
80///
81/// See <https://www.rerun.io/docs/concepts/entity-path> for more on entity paths.
82///
83/// This is basically implemented as a list of strings, but is reference-counted internally, so it is cheap to clone.
84/// It also has a precomputed hash and implemented [`nohash_hasher::IsEnabled`],
85/// so it is very cheap to use in a [`nohash_hasher::IntMap`] and [`nohash_hasher::IntSet`].
86///
87/// ```
88/// # use re_log_types::EntityPath;
89/// assert_eq!(
90///     EntityPath::parse_strict(r#"camera/ACME\ Örnöga/points/42"#).unwrap(),
91///     EntityPath::new(vec![
92///         "camera".into(),
93///         "ACME Örnöga".into(),
94///         "points".into(),
95///         "42".into(),
96///     ])
97/// );
98/// ```
99#[derive(Clone, Eq)]
100pub struct EntityPath {
101    /// precomputed hash
102    hash: EntityPathHash,
103
104    // [`Arc`] used for cheap cloning, and to keep down the size of [`EntityPath`].
105    // We mostly use the hash for lookups and comparisons anyway!
106    parts: Arc<Vec<EntityPathPart>>,
107}
108
109impl EntityPath {
110    #[inline]
111    pub fn root() -> Self {
112        Self::from(vec![])
113    }
114
115    /// The reserved namespace for properties.
116    #[inline]
117    pub fn properties() -> Self {
118        Self::from(vec![EntityPathPart::properties()])
119    }
120
121    /// The reserved namespace for the `RecordingProperties` that are specific to the Rerun viewer.
122    #[inline]
123    pub fn recording_properties() -> Self {
124        Self::from(vec![
125            EntityPathPart::properties(),
126            EntityPathPart::recording(),
127        ])
128    }
129
130    /// Returns `true` if the [`EntityPath`] belongs to a reserved namespace.
131    ///
132    /// Returns `true` iff the root entity starts with `__`.
133    #[inline]
134    pub fn is_reserved(&self) -> bool {
135        self.iter()
136            .next()
137            .is_some_and(|part| part.unescaped_str().starts_with(RESERVED_NAMESPACE_PREFIX))
138    }
139
140    #[inline]
141    pub fn new(parts: Vec<EntityPathPart>) -> Self {
142        Self::from(parts)
143    }
144
145    /// Treat the file path as one opaque string.
146    ///
147    /// The file path separators will NOT become splits in the new path.
148    /// The returned path will only have one part.
149    pub fn from_file_path_as_single_string(file_path: &std::path::Path) -> Self {
150        Self::from_single_string(file_path.to_string_lossy().to_string())
151    }
152
153    /// Treat the file path as an entity path hierarchy.
154    ///
155    /// The file path separators will become splits in the new path.
156    pub fn from_file_path(file_path: &std::path::Path) -> Self {
157        use clean_path::Clean as _;
158        Self::new(
159            file_path
160                .clean()
161                .iter()
162                .map(|p| EntityPathPart::from(p.to_string_lossy().to_string()))
163                .collect(),
164        )
165    }
166
167    /// Treat the string as one opaque string, NOT splitting on any slashes.
168    ///
169    /// The given string is expected to be unescaped, i.e. any `\` is treated as a normal character.
170    pub fn from_single_string(string: impl Into<InternedString>) -> Self {
171        Self::new(vec![EntityPathPart::new(string)])
172    }
173
174    #[inline]
175    pub fn iter(&self) -> impl DoubleEndedIterator<Item = &EntityPathPart> + ExactSizeIterator {
176        self.parts.iter()
177    }
178
179    #[inline]
180    pub fn last(&self) -> Option<&EntityPathPart> {
181        self.parts.last()
182    }
183
184    #[inline]
185    pub fn as_slice(&self) -> &[EntityPathPart] {
186        self.parts.as_slice()
187    }
188
189    #[inline]
190    pub fn to_vec(&self) -> Vec<EntityPathPart> {
191        self.parts.to_vec()
192    }
193
194    #[inline]
195    pub fn is_root(&self) -> bool {
196        self.parts.is_empty()
197    }
198
199    /// Is this equals to, or a descendant of, the given path.
200    #[inline]
201    pub fn starts_with(&self, prefix: &Self) -> bool {
202        if self.hash == prefix.hash {
203            return true; // optimization!
204        }
205
206        prefix.len() <= self.len() && self.iter().zip(prefix.iter()).all(|(a, b)| a == b)
207    }
208
209    /// Is this a strict descendant of the given path.
210    #[inline]
211    pub fn is_descendant_of(&self, other: &Self) -> bool {
212        other.len() < self.len() && self.iter().zip(other.iter()).all(|(a, b)| a == b)
213    }
214
215    /// Is this a direct child of the other path.
216    #[inline]
217    pub fn is_child_of(&self, other: &Self) -> bool {
218        other.len() + 1 == self.len() && self.iter().zip(other.iter()).all(|(a, b)| a == b)
219    }
220
221    /// Number of parts
222    #[inline]
223    #[allow(clippy::len_without_is_empty)]
224    pub fn len(&self) -> usize {
225        self.parts.len()
226    }
227
228    #[inline]
229    pub fn hash(&self) -> EntityPathHash {
230        self.hash
231    }
232
233    /// Precomputed 64-bit hash.
234    #[inline]
235    pub fn hash64(&self) -> u64 {
236        self.hash.hash64()
237    }
238
239    /// Return [`None`] if root.
240    #[must_use]
241    pub fn parent(&self) -> Option<Self> {
242        self.parts
243            .len()
244            .checked_sub(1)
245            .map(|n_minus_1| Self::new(self.parts[..n_minus_1].to_vec()))
246    }
247
248    pub fn join(&self, other: &Self) -> Self {
249        self.iter().chain(other.iter()).cloned().collect()
250    }
251
252    /// Helper function to iterate over all incremental [`EntityPath`]s from start to end, NOT including start itself.
253    ///
254    /// For example `incremental_walk("foo", "foo/bar/baz")` returns: `["foo/bar", "foo/bar/baz"]`
255    pub fn incremental_walk<'a>(
256        start: Option<&'_ Self>,
257        end: &'a Self,
258    ) -> impl Iterator<Item = Self> + 'a + use<'a> {
259        re_tracing::profile_function!();
260        if start.is_none_or(|start| end.is_descendant_of(start)) {
261            let first_ind = start.map_or(0, |start| start.len() + 1);
262            let parts = end.as_slice();
263            itertools::Either::Left((first_ind..=end.len()).map(|i| Self::from(&parts[0..i])))
264        } else {
265            itertools::Either::Right(std::iter::empty())
266        }
267    }
268
269    /// Returns the first common ancestor of two paths.
270    ///
271    /// If both paths are the same, the common ancestor is the path itself.
272    pub fn common_ancestor(&self, other: &Self) -> Self {
273        let mut common = Vec::new();
274        for (a, b) in self.iter().zip(other.iter()) {
275            if a == b {
276                common.push(a.clone());
277            } else {
278                break;
279            }
280        }
281        Self::new(common)
282    }
283
284    /// Returns the first common ancestor of a list of entity paths.
285    pub fn common_ancestor_of<'a>(mut entities: impl Iterator<Item = &'a Self>) -> Self {
286        let first = entities.next().cloned().unwrap_or(Self::root());
287        entities.fold(first, |acc, e| acc.common_ancestor(e))
288    }
289
290    /// Returns short names for a collection of entities based on the last part(s), ensuring
291    /// uniqueness. Disambiguation is achieved by increasing the number of entity parts used.
292    ///
293    /// Note: the result is undefined when the input contains duplicates.
294    pub fn short_names_with_disambiguation(
295        entities: impl IntoIterator<Item = Self>,
296    ) -> HashMap<Self, String> {
297        struct ShortenedEntity {
298            entity: EntityPath,
299
300            /// How many parts (from the end) to use for the short name
301            num_part: usize,
302        }
303
304        impl ShortenedEntity {
305            fn ui_string(&self) -> String {
306                if self.entity.parts.is_empty() {
307                    return "/".to_owned();
308                }
309
310                self.entity
311                    .iter()
312                    .rev()
313                    .take(self.num_part)
314                    .rev()
315                    .map(|part| part.ui_string())
316                    .join("/")
317            }
318        }
319
320        let mut str_to_entities: HashMap<String, ShortenedEntity> = HashMap::default();
321        let mut known_bad_labels: HashSet<String> = HashSet::default();
322
323        for entity in entities {
324            let mut shortened = ShortenedEntity {
325                entity,
326                num_part: 1,
327            };
328
329            loop {
330                let new_label = shortened.ui_string();
331
332                if str_to_entities.contains_key(&new_label) || known_bad_labels.contains(&new_label)
333                {
334                    // we have a conflict so:
335                    // - we fix the previously added entity by increasing its `num_part`
336                    // - we increase the `num_part` of the current entity
337                    // - we record this label as bad
338
339                    known_bad_labels.insert(new_label.clone());
340
341                    if let Some(mut existing_shortened) = str_to_entities.remove(&new_label) {
342                        existing_shortened.num_part += 1;
343                        str_to_entities.insert(existing_shortened.ui_string(), existing_shortened);
344                    }
345
346                    shortened.num_part += 1;
347                    if shortened.ui_string() == new_label {
348                        // we must have reached the root for this entity, so we bail out to avoid
349                        // an infinite loop
350                        break;
351                    }
352                } else {
353                    break;
354                }
355            }
356
357            str_to_entities.insert(shortened.ui_string(), shortened);
358        }
359
360        str_to_entities
361            .into_iter()
362            .map(|(str, entity)| (entity.entity, str))
363            .collect()
364    }
365}
366
367impl SizeBytes for EntityPath {
368    #[inline]
369    fn heap_size_bytes(&self) -> u64 {
370        0 // NOTE: we assume it's amortized due to the `Arc`
371    }
372}
373
374impl FromIterator<EntityPathPart> for EntityPath {
375    fn from_iter<T: IntoIterator<Item = EntityPathPart>>(parts: T) -> Self {
376        Self::new(parts.into_iter().collect())
377    }
378}
379
380impl From<Vec<EntityPathPart>> for EntityPath {
381    #[inline]
382    fn from(path: Vec<EntityPathPart>) -> Self {
383        Self {
384            hash: EntityPathHash(Hash64::hash(&path)),
385            parts: Arc::new(path),
386        }
387    }
388}
389
390impl From<&[EntityPathPart]> for EntityPath {
391    #[inline]
392    fn from(path: &[EntityPathPart]) -> Self {
393        Self::from(path.to_vec())
394    }
395}
396
397impl From<&str> for EntityPath {
398    #[inline]
399    fn from(path: &str) -> Self {
400        Self::parse_forgiving(path)
401    }
402}
403
404impl From<String> for EntityPath {
405    #[inline]
406    fn from(path: String) -> Self {
407        Self::parse_forgiving(&path)
408    }
409}
410
411impl From<EntityPath> for String {
412    #[inline]
413    fn from(path: EntityPath) -> Self {
414        path.to_string()
415    }
416}
417
418impl From<re_types_core::datatypes::EntityPath> for EntityPath {
419    #[inline]
420    fn from(value: re_types_core::datatypes::EntityPath) -> Self {
421        Self::parse_forgiving(&value.0)
422    }
423}
424
425impl From<&EntityPath> for re_types_core::datatypes::EntityPath {
426    #[inline]
427    fn from(value: &EntityPath) -> Self {
428        Self(value.to_string().into())
429    }
430}
431
432impl<Idx> std::ops::Index<Idx> for EntityPath
433where
434    Idx: std::slice::SliceIndex<[EntityPathPart]>,
435{
436    type Output = Idx::Output;
437
438    #[inline]
439    fn index(&self, index: Idx) -> &Self::Output {
440        &self.parts[index]
441    }
442}
443
444// ----------------------------------------------------------------------------
445
446impl std::ops::Div<Self> for EntityPath {
447    type Output = Self;
448
449    #[inline]
450    fn div(self, other: Self) -> Self::Output {
451        self.join(&other)
452    }
453}
454
455impl std::ops::Div<Self> for &EntityPath {
456    type Output = EntityPath;
457
458    #[inline]
459    fn div(self, other: Self) -> Self::Output {
460        self.join(other)
461    }
462}
463
464impl std::ops::Div<EntityPathPart> for EntityPath {
465    type Output = Self;
466
467    #[inline]
468    fn div(self, other: EntityPathPart) -> Self::Output {
469        self.join(&Self::new(vec![other]))
470    }
471}
472
473impl std::ops::Div<EntityPathPart> for &EntityPath {
474    type Output = EntityPath;
475
476    #[inline]
477    fn div(self, other: EntityPathPart) -> Self::Output {
478        self.join(&EntityPath::new(vec![other]))
479    }
480}
481
482// ----------------------------------------------------------------------------
483
484use re_types_core::Loggable;
485
486use super::entity_path_part::RESERVED_NAMESPACE_PREFIX;
487
488re_types_core::macros::impl_into_cow!(EntityPath);
489
490impl Loggable for EntityPath {
491    #[inline]
492    fn arrow_datatype() -> arrow::datatypes::DataType {
493        re_types_core::datatypes::Utf8::arrow_datatype()
494    }
495
496    fn to_arrow_opt<'a>(
497        _data: impl IntoIterator<Item = Option<impl Into<std::borrow::Cow<'a, Self>>>>,
498    ) -> re_types_core::SerializationResult<arrow::array::ArrayRef>
499    where
500        Self: 'a,
501    {
502        Err(re_types_core::SerializationError::not_implemented(
503            "rerun.controls.EntityPath",
504            "EntityPaths are never nullable, use `to_arrow()` instead",
505        ))
506    }
507
508    #[inline]
509    fn to_arrow<'a>(
510        data: impl IntoIterator<Item = impl Into<std::borrow::Cow<'a, Self>>>,
511    ) -> re_types_core::SerializationResult<arrow::array::ArrayRef>
512    where
513        Self: 'a,
514    {
515        re_types_core::datatypes::Utf8::to_arrow(
516            data.into_iter()
517                .map(Into::into)
518                .map(|ent_path| re_types_core::datatypes::Utf8(ent_path.to_string().into())),
519        )
520    }
521
522    fn from_arrow(
523        array: &dyn ::arrow::array::Array,
524    ) -> re_types_core::DeserializationResult<Vec<Self>> {
525        Ok(re_types_core::datatypes::Utf8::from_arrow(array)?
526            .into_iter()
527            .map(|utf8| Self::from(utf8.to_string()))
528            .collect())
529    }
530}
531
532// ----------------------------------------------------------------------------
533
534#[cfg(feature = "serde")]
535impl serde::Serialize for EntityPath {
536    #[inline]
537    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
538        self.parts.serialize(serializer)
539    }
540}
541
542#[cfg(feature = "serde")]
543impl<'de> serde::Deserialize<'de> for EntityPath {
544    #[inline]
545    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
546        let parts = Vec::<EntityPathPart>::deserialize(deserializer)?;
547        Ok(Self::new(parts))
548    }
549}
550
551// ----------------------------------------------------------------------------
552
553impl std::cmp::PartialEq for EntityPath {
554    #[inline]
555    fn eq(&self, other: &Self) -> bool {
556        self.hash == other.hash // much faster, and low risk of collision
557    }
558}
559
560impl std::hash::Hash for EntityPath {
561    #[inline]
562    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
563        self.hash.hash(state);
564    }
565}
566
567impl nohash_hasher::IsEnabled for EntityPath {}
568
569// ----------------------------------------------------------------------------
570
571impl std::cmp::Ord for EntityPath {
572    #[inline]
573    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
574        self.parts.cmp(&other.parts)
575    }
576}
577
578impl std::cmp::PartialOrd for EntityPath {
579    #[inline]
580    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
581        Some(self.parts.cmp(&other.parts))
582    }
583}
584
585// ----------------------------------------------------------------------------
586
587impl std::fmt::Debug for EntityPath {
588    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
589        // Same as `Display` - since we always prefix paths with a slash, they are easily recognizable.
590        write!(f, "{self}")
591    }
592}
593
594impl std::fmt::Display for EntityPath {
595    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
596        use std::fmt::Write as _;
597
598        if self.is_root() {
599            f.write_char('/')
600        } else {
601            // We always lead with a slash
602            for comp in self.iter() {
603                f.write_char('/')?;
604                comp.escaped_string().fmt(f)?;
605            }
606            Ok(())
607        }
608    }
609}
610
611// ----------------------------------------------------------------------------
612
613#[cfg(test)]
614mod tests {
615    use super::*;
616
617    #[test]
618    fn test_root() {
619        assert_eq!(EntityPath::root(), EntityPath::from("/"));
620    }
621
622    #[test]
623    fn test_properties() {
624        let path = EntityPath::properties();
625        assert_eq!(path, EntityPath::from("/__properties"));
626        assert!(path.is_reserved());
627    }
628
629    #[test]
630    fn test_recording_properties() {
631        let path = EntityPath::recording_properties();
632        assert_eq!(path, EntityPath::from("/__properties/recording"),);
633        assert!(path.is_reserved());
634    }
635
636    #[test]
637    fn test_incremental_walk() {
638        assert_eq!(
639            EntityPath::incremental_walk(None, &EntityPath::root()).collect::<Vec<_>>(),
640            vec![EntityPath::root()]
641        );
642        assert_eq!(
643            EntityPath::incremental_walk(Some(&EntityPath::root()), &EntityPath::root())
644                .collect::<Vec<_>>(),
645            vec![]
646        );
647        assert_eq!(
648            EntityPath::incremental_walk(None, &EntityPath::from("foo")).collect::<Vec<_>>(),
649            vec![EntityPath::root(), EntityPath::from("foo")]
650        );
651        assert_eq!(
652            EntityPath::incremental_walk(Some(&EntityPath::root()), &EntityPath::from("foo"))
653                .collect::<Vec<_>>(),
654            vec![EntityPath::from("foo")]
655        );
656        assert_eq!(
657            EntityPath::incremental_walk(None, &EntityPath::from("foo/bar")).collect::<Vec<_>>(),
658            vec![
659                EntityPath::root(),
660                EntityPath::from("foo"),
661                EntityPath::from("foo/bar")
662            ]
663        );
664        assert_eq!(
665            EntityPath::incremental_walk(
666                Some(&EntityPath::from("foo")),
667                &EntityPath::from("foo/bar/baz")
668            )
669            .collect::<Vec<_>>(),
670            vec![EntityPath::from("foo/bar"), EntityPath::from("foo/bar/baz")]
671        );
672    }
673
674    #[test]
675    fn test_common_ancestor() {
676        assert_eq!(
677            EntityPath::from("foo/bar").common_ancestor(&EntityPath::from("foo/bar")),
678            EntityPath::from("foo/bar")
679        );
680        assert_eq!(
681            EntityPath::from("foo/bar").common_ancestor(&EntityPath::from("foo/bar/baz")),
682            EntityPath::from("foo/bar")
683        );
684        assert_eq!(
685            EntityPath::from("foo/bar/baz").common_ancestor(&EntityPath::from("foo/bar")),
686            EntityPath::from("foo/bar")
687        );
688        assert_eq!(
689            EntityPath::from("foo/bar/mario").common_ancestor(&EntityPath::from("foo/bar/luigi")),
690            EntityPath::from("foo/bar")
691        );
692        assert_eq!(
693            EntityPath::from("mario/bowser").common_ancestor(&EntityPath::from("luigi/bowser")),
694            EntityPath::root()
695        );
696    }
697
698    #[test]
699    fn test_short_names_with_disambiguation() {
700        fn run_test(entities: &[(&str, &str)]) {
701            let paths = entities
702                .iter()
703                .map(|(entity, _)| EntityPath::from(*entity))
704                .collect_vec();
705            let result = EntityPath::short_names_with_disambiguation(paths.clone());
706
707            for (path, shortened) in paths.iter().zip(entities.iter().map(|e| e.1)) {
708                assert_eq!(result[path], shortened);
709            }
710        }
711
712        // --
713
714        run_test(&[("foo/bar", "bar"), ("qaz/bor", "bor")]);
715
716        run_test(&[
717            ("hello/world", "world"),
718            ("bim/foo/bar", "foo/bar"),
719            ("bim/qaz/bar", "qaz/bar"),
720            ("a/x/y/z", "a/x/y/z"),
721            ("b/x/y/z", "b/x/y/z"),
722            ("c/d/y/z", "d/y/z"),
723        ]);
724
725        run_test(&[("/", "/"), ("/a", "a")]);
726
727        // degenerate cases
728        run_test(&[("/", "/"), ("/", "/")]);
729        run_test(&[("a/b", "a/b"), ("a/b", "a/b")]);
730    }
731}
re_log_types/path/entity_path.rs

re_log_types/path/
entity_path.rs
