source_tools/
span.rs

1use crate::SourceOffset;
2use allocator_api2::alloc::{Allocator, Global};
3use allocator_api2::boxed::Box;
4use core::{fmt::Display, hash::Hash, marker::PhantomData, ops::Add};
5
6/// A half-open byte range in source text.
7#[repr(C)]
8#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
9#[cfg_attr(feature = "serde", derive(serde::Serialize))]
10pub struct Span {
11	start: SourceOffset,
12	end: SourceOffset,
13}
14
15impl Span {
16	/// A synthetic span.
17	pub const DUMMY: Self = Self::new(SourceOffset::DUMMY, SourceOffset::DUMMY);
18
19	/// An empty span at start of source text.
20	pub const ZERO: Self = Self::new(SourceOffset::ZERO, SourceOffset::ZERO);
21
22	/// Creates a span between two offsets.
23	#[inline]
24	pub const fn new(start: SourceOffset, end: SourceOffset) -> Self {
25		debug_assert!(start.0 <= end.0);
26		Self { start, end }
27	}
28
29	/// Returns starting offset.
30	#[inline]
31	pub const fn start(&self) -> SourceOffset {
32		self.start
33	}
34
35	/// Returns ending offset.
36	#[inline]
37	pub const fn end(&self) -> SourceOffset {
38		self.end
39	}
40
41	/// Returns a copy ending at `end`.
42	#[inline]
43	pub const fn with_end(self, end: SourceOffset) -> Self {
44		debug_assert!(self.start.0 <= end.0);
45		Self { start: self.start, end }
46	}
47
48	/// Returns whether `span` is entirely within this span.
49	pub const fn contains(&self, span: Span) -> bool {
50		self.start.0 <= span.start.0 && span.end.0 <= self.end.0
51	}
52
53	/// Returns whether spans share at least one byte.
54	pub const fn overlaps(&self, span: Span) -> bool {
55		self.start.0 < span.end.0 && span.start.0 < self.end.0
56	}
57
58	/// Returns whether span contains no bytes.
59	pub const fn is_empty(&self) -> bool {
60		self.start.0 == self.end.0
61	}
62
63	/// Returns length in bytes.
64	pub const fn len(&self) -> u32 {
65		debug_assert!(self.start.0 <= self.end.0);
66		self.end.0 - self.start.0
67	}
68
69	/// Returns covered source text.
70	pub fn str_slice<'a>(&self, source: &'a str) -> &'a str {
71		&source[self.start.0 as usize..self.end.0 as usize]
72	}
73
74	/// Returns zero-based line and column of span start.
75	pub fn line_and_column(self, source: &str) -> (u32, u32) {
76		let mut line = 0;
77		let mut column = 0;
78		let mut offset = self.start.0;
79		for character in source.chars() {
80			if offset == 0 {
81				break;
82			}
83			if character == '\n' {
84				column = 0;
85				line += 1;
86			} else {
87				column += 1;
88			}
89			offset -= character.len_utf8() as u32;
90		}
91		(line, column)
92	}
93}
94
95/// Precomputed line starts for repeated line and column lookup.
96#[derive(Debug, Clone)]
97pub struct LineIndex<'a, A: Allocator = Global> {
98	source: &'a str,
99	line_starts: Box<[u32], A>,
100}
101
102impl<'a> LineIndex<'a, Global> {
103	/// Builds an index for `source`.
104	pub fn new(source: &'a str) -> Self {
105		Self::new_in(source, Global)
106	}
107}
108
109impl<'a, A: Allocator> LineIndex<'a, A> {
110	/// Builds an index using `alloc`.
111	pub fn new_in(source: &'a str, alloc: A) -> Self {
112		let mut line_starts = allocator_api2::vec::Vec::with_capacity_in(source.len() / 32 + 1, alloc);
113		line_starts.push(0);
114		for (index, byte) in source.bytes().enumerate() {
115			if byte == b'\n' {
116				line_starts.push(index as u32 + 1);
117			}
118		}
119		Self { source, line_starts: line_starts.into_boxed_slice() }
120	}
121
122	/// Returns zero-based line and column of span start.
123	pub fn line_and_column(&self, span: Span) -> (u32, u32) {
124		let starts = &self.line_starts[..];
125		let offset = span.start().0;
126		let line = starts.partition_point(|&start| start <= offset) - 1;
127		let line_start = starts[line] as usize;
128		let end = (offset as usize).min(self.source.len());
129		let column = self.source[line_start..end].chars().count() as u32;
130		(line as u32, column)
131	}
132}
133
134impl Add for Span {
135	type Output = Self;
136
137	fn add(self, rhs: Self) -> Self::Output {
138		if rhs == Self::DUMMY {
139			return self;
140		}
141		if self == Self::DUMMY {
142			return rhs;
143		}
144		Self { start: SourceOffset(self.start.0.min(rhs.start.0)), end: SourceOffset(self.end.0.max(rhs.end.0)) }
145	}
146}
147
148impl Display for Span {
149	fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
150		write!(f, "[{}..{})", self.start.0, self.end.0)
151	}
152}
153
154#[cfg(feature = "miette")]
155impl From<Span> for miette::SourceSpan {
156	fn from(value: Span) -> Self {
157		Self::new(miette::SourceOffset::from(value.start.0 as usize), value.len() as usize)
158	}
159}
160
161/// A value that can return its source span.
162pub trait ToSpan {
163	/// Returns source span.
164	fn to_span(&self) -> Span;
165}
166
167impl ToSpan for Span {
168	fn to_span(&self) -> Span {
169		*self
170	}
171}
172
173impl<T: ToSpan> ToSpan for &T {
174	fn to_span(&self) -> Span {
175		(**self).to_span()
176	}
177}
178
179impl<T: ToSpan> ToSpan for &mut T {
180	fn to_span(&self) -> Span {
181		(**self).to_span()
182	}
183}
184
185impl<T: ToSpan> ToSpan for Option<T> {
186	fn to_span(&self) -> Span {
187		self.as_ref().map_or(Span::DUMMY, ToSpan::to_span)
188	}
189}
190
191impl<T> ToSpan for PhantomData<T> {
192	fn to_span(&self) -> Span {
193		Span::DUMMY
194	}
195}
196
197impl<T: ToSpan> ToSpan for [T] {
198	fn to_span(&self) -> Span {
199		self.iter().fold(Span::DUMMY, |span, item| span + item.to_span())
200	}
201}
202
203impl<T: ToSpan> ToSpan for Vec<T> {
204	fn to_span(&self) -> Span {
205		self.as_slice().to_span()
206	}
207}
208
209impl<T: ToSpan, A: Allocator> ToSpan for allocator_api2::vec::Vec<T, A> {
210	fn to_span(&self) -> Span {
211		self.as_slice().to_span()
212	}
213}
214
215macro_rules! impl_tuple {
216	($($name:ident),+) => {
217		impl<$($name: ToSpan),+> ToSpan for ($($name,)+) {
218			#[allow(non_snake_case)]
219			fn to_span(&self) -> Span {
220				let ($($name,)+) = self;
221				Span::DUMMY $(+ $name.to_span())+
222			}
223		}
224	};
225}
226
227impl_tuple!(A, B);
228impl_tuple!(A, B, C);
229impl_tuple!(A, B, C, D);
230impl_tuple!(A, B, C, D, E);
231impl_tuple!(A, B, C, D, E, F);
232impl_tuple!(A, B, C, D, E, F, G);
233impl_tuple!(A, B, C, D, E, F, G, H);
234impl_tuple!(A, B, C, D, E, F, G, H, I);
235impl_tuple!(A, B, C, D, E, F, G, H, I, J);
236impl_tuple!(A, B, C, D, E, F, G, H, I, J, K);
237impl_tuple!(A, B, C, D, E, F, G, H, I, J, K, L);
238
239#[cfg(test)]
240mod tests {
241	use super::*;
242
243	#[test]
244	fn span_layout_and_ranges() {
245		let span = Span::new(SourceOffset(2), SourceOffset(5));
246		assert_eq!(size_of::<Span>(), 8);
247		assert_eq!(span.len(), 3);
248		assert_eq!(span.str_slice("abcdef"), "cde");
249		assert!(span.contains(Span::new(SourceOffset(3), SourceOffset(4))));
250		assert!(!span.overlaps(Span::new(SourceOffset(5), SourceOffset(6))));
251	}
252
253	#[test]
254	fn empty_collections_have_dummy_span() {
255		let spans: Vec<Span> = vec![];
256		assert_eq!(spans.to_span(), Span::DUMMY);
257	}
258
259	#[test]
260	fn line_index_matches_scan() {
261		let source = "one\ntwø\nthree";
262		let index = LineIndex::new(source);
263		for offset in source.char_indices().map(|(offset, _)| offset).chain([source.len()]) {
264			let offset = offset as u32;
265			let span = Span::new(SourceOffset(offset), SourceOffset(offset));
266			assert_eq!(index.line_and_column(span), span.line_and_column(source));
267		}
268	}
269}
source_tools/span.rs

source_tools/
span.rs
