compose_syntax/
span.rs

1use crate::file::{FileId, VirtualPath};
2use std::fmt::{Debug, Formatter};
3use std::num::{NonZeroU16, NonZeroU64};
4use std::ops::Range;
5use std::path::{Path, PathBuf};
6use crate::SyntaxNode;
7
8/// Defines a range in a source file.
9#[derive(Clone, Copy, Eq, PartialEq, Ord, PartialOrd, Hash)]
10pub struct Span(NonZeroU64);
11
12impl Span {
13    /// A Span that does not point anywhere
14    const DETACHED: u64 = 1;
15
16    /// Data Layout:
17    ///
18    /// | 16 bits FileId | 48 bits Range |
19    ///
20    /// Range =
21    /// - 1 means detached
22    /// - rest is range
23    const RANGE_BITS: usize = 48;
24
25    const ATTACHED_RANGE: Range<u64> = 2..(1 << 48);
26    const FILE_ID_SHIFT: usize = Self::RANGE_BITS;
27    const ATTACHED_RANGE_START: u64 = Self::ATTACHED_RANGE.start;
28
29    /// The number of bits in each part of the lower or higher bound of the range
30    const RANGE_PART_BITS: usize = 24;
31
32    const RANGE_PART_MASK: u64 = (1 << Self::RANGE_PART_BITS) - 1;
33    const RANGE_MASK: u64 = (1 << Self::RANGE_BITS) - 1;
34
35    /// Create a span that does not point to any file.
36    pub const fn detached() -> Self {
37        match NonZeroU64::new(Self::DETACHED) {
38            Some(v) => Self(v),
39            None => unreachable!(),
40        }
41    }
42
43    /// Returns a new span with the given FileId and range
44    pub(crate) const fn new(id: FileId, range: Range<usize>) -> Self {
45        let range_as_number = Self::range_as_number(range);
46
47        Self::pack(id, range_as_number)
48    }
49
50    /// Returns the range in the following format;
51    /// | start (24 bits) | end (24 bits) |
52    const fn range_as_number(range: Range<usize>) -> u64 {
53        let max = (1 << Self::RANGE_PART_BITS) - Self::ATTACHED_RANGE_START as usize;
54
55        debug_assert!(range.start <= max, "range.start too large");
56        debug_assert!(range.end <= max, "range.end too large");
57
58        let range_start = Self::min(range.start, max) as u64;
59        let range_end = Self::min(range.end, max) as u64;
60
61        (range_start << Self::RANGE_PART_BITS) | range_end
62    }
63
64    /// Packs a file id and a range
65    const fn pack(id: FileId, range_as_number: u64) -> Self {
66        let bits = ((id.into_raw().get() as u64) << Self::FILE_ID_SHIFT)
67            | (range_as_number + Self::ATTACHED_RANGE_START);
68        match NonZeroU64::new(bits) {
69            Some(v) => Self(v),
70            None => unreachable!(),
71        }
72    }
73
74    pub const fn is_detached(self) -> bool {
75        self.0.get() == Self::DETACHED
76    }
77
78    pub const fn id(self) -> Option<FileId> {
79        match NonZeroU16::new((self.0.get() >> Self::FILE_ID_SHIFT) as u16) {
80            None => None,
81            Some(v) => Some(FileId::from_raw(v)),
82        }
83    }
84
85    pub fn range(self) -> Option<Range<usize>> {
86        if self.is_detached() {
87            return None;
88        }
89
90        let number = (self.0.get() & Self::RANGE_MASK) - Self::ATTACHED_RANGE_START;
91
92        let start = (number >> Self::RANGE_PART_BITS) as usize;
93        let end = (number & Self::RANGE_PART_MASK) as usize;
94
95        Some(start..end)
96    }
97    
98    pub fn len(self) -> Option<usize> {
99        self.range().map(|r| r.len())   
100    }
101
102    pub fn join(left: Span, right: Span) -> Span {
103        if left.id() != right.id() {
104            return left.or(right);
105        }
106
107        let id = left.or(right).id().unwrap();
108
109        let (start, end) = match (left.range(), right.range()) {
110            (None, _) => return right,
111            (_, None) => return left,
112            (Some(l), Some(r)) => (l.start.min(r.start), r.end.max(l.end)),
113        };
114
115        Span::new(id, start..end)
116    }
117
118    pub fn resolve_path(self, relative_path: impl AsRef<Path>) -> Option<VirtualPath> {
119        let id = self.id()?;
120        let base = id.path().0.clone().parent()?.to_path_buf();
121
122        let relative_path = relative_path.as_ref();
123        let path = if relative_path.is_absolute() {
124            relative_path.to_path_buf()
125        } else {
126            PathBuf::from(&base)
127                .canonicalize()
128                .unwrap_or(PathBuf::from(&base))
129                .join(relative_path)
130        };
131
132        Some(VirtualPath::new(path))
133    }
134
135    pub fn or(self, other: Span) -> Span {
136        if self.is_detached() {
137            return other;
138        }
139        self
140    }
141
142    pub fn after(self) -> Self {
143        if self.is_detached() {
144            return self;
145        }
146
147        let range = self.range().unwrap();
148        let end = range.end;
149        let at = end;
150
151        Span::new(self.id().unwrap(), at..at + 1)
152    }
153}
154
155impl Span {
156    #[inline]
157    const fn min(a: usize, b: usize) -> usize {
158        if a <= b { a } else { b }
159    }
160}
161
162impl Debug for Span {
163    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
164        let id = match self.id() {
165            Some(id) => id
166                .try_path()
167                .map(|p| p.display())
168                .unwrap_or_else(|| "Unknown".to_string()),
169            None => "Detached".to_string(),
170        };
171
172        let range = match self.range() {
173            Some(range) => format!(":{:?}", range),
174            None => "".to_string(),
175        };
176
177        write!(f, "{}{}", id, range)
178    }
179}
180
181pub trait HasSpan {
182    fn span(&self) -> Span;
183}
184
185impl HasSpan for Span {
186    fn span(&self) -> Span {
187        *self
188    }
189}
190
191impl HasSpan for SyntaxNode {
192    fn span(&self) -> Span {
193        self.span()
194    }
195}
196
197#[cfg(test)]
198mod tests {
199    use crate::file::FileId;
200    use crate::span::Span;
201    use crate::test_utils::test_file_id;
202    use std::num::NonZeroU16;
203    use std::ops::Range;
204
205    #[test]
206    fn test_range_as_number() {
207        assert_eq!(
208            Span::range_as_number(2..4),
209            0b0000_0000_0000_0000_0000_0010_0000_0000_0000_0000_0000_0100u64
210        );
211    }
212
213    #[test]
214    fn pack_and_unpack_file_id() {
215        let packed = Span::pack(test_file_id(), 0);
216        assert_eq!(packed.id(), Some(test_file_id()));
217        assert_eq!(packed.range(), Some(0..0));
218    }
219
220    #[test]
221    fn test_detached() {
222        let span = Span::detached();
223        assert!(span.is_detached());
224        assert_eq!(span.id(), None);
225        assert_eq!(span.range(), None);
226    }
227
228    #[test]
229    fn test_from_range() {
230        let id = FileId::from_raw(NonZeroU16::new(1).unwrap());
231
232        let round_trip = |range: Range<usize>| {
233            let span = Span::new(id, range.clone());
234            assert_eq!(span.id(), Some(id));
235            assert_eq!(span.range(), Some(range));
236        };
237
238        round_trip(0..0);
239        round_trip(0..1);
240        round_trip(2..4);
241        round_trip(100..100);
242        round_trip(12_101..12_211);
243    }
244}
compose_syntax/span.rs

compose_syntax/
span.rs
