syntree/
index.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
//! Types that can be used to refer to indexes in a [Span][crate::Span].

use core::cmp;

use crate::flavor::Flavor;

mod sealed {
    pub trait Sealed {}

    impl Sealed for u32 {}
    impl Sealed for usize {}
    impl Sealed for crate::empty::Empty {}
}

/// A type that can be used when referring to an index in a tree.
///
/// An index is a valid single component of a [Span][crate::Span], valid indexes
/// are types such as `u32` and `usize`, but also [`Empty`][crate::Empty] in
/// case indexing is not required.
///
/// See [Builder::new_with][crate::Builder::new_with].
pub trait Index: Sized + Copy + cmp::Ord + cmp::Eq + self::sealed::Sealed {
    #[doc(hidden)]
    const EMPTY: Self;

    #[doc(hidden)]
    type Length: Length;

    #[doc(hidden)]
    fn is_empty(&self) -> bool;

    #[doc(hidden)]
    fn as_usize(self) -> usize;

    #[doc(hidden)]
    fn checked_add_len(self, other: Self::Length) -> Option<Self>;

    #[doc(hidden)]
    fn len_to(self, other: Self) -> Self::Length;

    #[doc(hidden)]
    fn from_usize(value: usize) -> Option<Self>;
}

#[doc(hidden)]
pub trait Length: Copy + self::sealed::Sealed {
    #[doc(hidden)]
    const EMPTY: Self;

    #[doc(hidden)]
    fn is_empty(&self) -> bool;
}

impl Length for usize {
    const EMPTY: Self = 0;

    #[inline]
    fn is_empty(&self) -> bool {
        *self == 0
    }
}

/// Ensure u32 is smaller or equal to usize.
const _: () = assert!(core::mem::size_of::<u32>() <= core::mem::size_of::<usize>());

impl Index for u32 {
    const EMPTY: Self = 0;

    type Length = usize;

    #[inline]
    fn is_empty(&self) -> bool {
        *self == 0
    }

    #[inline]
    fn as_usize(self) -> usize {
        self as usize
    }

    #[inline]
    fn checked_add_len(self, other: Self::Length) -> Option<Self> {
        u32::checked_add(self, u32::try_from(other).ok()?)
    }

    #[inline]
    fn len_to(self, other: Self) -> Self::Length {
        other.saturating_sub(self) as usize
    }

    #[inline]
    fn from_usize(value: usize) -> Option<Self> {
        u32::try_from(value).ok()
    }
}

impl Index for usize {
    const EMPTY: Self = 0;

    type Length = usize;

    #[inline]
    fn is_empty(&self) -> bool {
        *self == 0
    }

    #[inline]
    fn as_usize(self) -> usize {
        self
    }

    #[inline]
    fn checked_add_len(self, other: Self::Length) -> Option<Self> {
        usize::checked_add(self, other)
    }

    #[inline]
    fn len_to(self, other: Self) -> Self::Length {
        other.saturating_sub(self)
    }

    #[inline]
    fn from_usize(value: usize) -> Option<Self> {
        Some(value)
    }
}

/// A single span index entry for the given [Flavor] `F`.
#[derive(Debug, Clone, Copy)]
#[doc(hidden)]
pub struct TreeIndex<F>
where
    F: ?Sized + Flavor,
{
    pub(crate) index: F::Index,
    pub(crate) id: F::Pointer,
}