span_lang/span.rs
1//! Byte-offset spans.
2
3use core::fmt;
4
5use crate::BytePos;
6
7/// A half-open byte range `start..end` into a single source.
8///
9/// A `Span` is two packed [`BytePos`] offsets — eight bytes, `Copy` — that a
10/// lexer attaches to every token and a parser threads through every node. The
11/// range is half-open: `start` is included, `end` is not, so the length is
12/// exactly `end - start` and adjacent spans (`a.end == b.start`) do not overlap.
13///
14/// # Invariant
15///
16/// `start <= end` always holds. [`Span::new`] enforces it by ordering its two
17/// arguments, so a span can never be constructed inverted, and every method may
18/// rely on it. An empty span (`start == end`) is legal and marks a zero-width
19/// point — the position of an insertion, or a token with no text.
20///
21/// Spans order lexicographically by `start` then `end`, so a slice of spans sorts
22/// into source order.
23///
24/// # Examples
25///
26/// ```
27/// use span_lang::Span;
28///
29/// let s = Span::new(4, 10);
30/// assert_eq!(s.len(), 6);
31/// assert!(!s.is_empty());
32///
33/// // Arguments are ordered, so an inverted call still yields a valid span.
34/// assert_eq!(Span::new(10, 4), Span::new(4, 10));
35/// ```
36#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
37pub struct Span {
38 start: u32,
39 end: u32,
40}
41
42impl Span {
43 /// Constructs a span covering `start..end`.
44 ///
45 /// If `start > end` the two are swapped, so the result always upholds the
46 /// `start <= end` invariant. This makes construction total — it never panics,
47 /// whatever offsets a caller supplies — which matters when the offsets come
48 /// from arithmetic on untrusted input.
49 ///
50 /// # Examples
51 ///
52 /// ```
53 /// use span_lang::Span;
54 ///
55 /// let s = Span::new(2, 7);
56 /// assert_eq!(s.start().to_u32(), 2);
57 /// assert_eq!(s.end().to_u32(), 7);
58 ///
59 /// // Ordering is normalised.
60 /// assert_eq!(Span::new(7, 2), s);
61 /// ```
62 #[inline]
63 #[must_use]
64 pub const fn new(start: u32, end: u32) -> Self {
65 if start <= end {
66 Self { start, end }
67 } else {
68 Self {
69 start: end,
70 end: start,
71 }
72 }
73 }
74
75 /// Constructs an empty, zero-width span at `at`.
76 ///
77 /// Equivalent to `Span::new(at, at)`. Use it to mark a point — for instance,
78 /// the caret position for an "expected token here" diagnostic.
79 ///
80 /// # Examples
81 ///
82 /// ```
83 /// use span_lang::Span;
84 ///
85 /// let point = Span::empty(5);
86 /// assert!(point.is_empty());
87 /// assert_eq!(point.len(), 0);
88 /// ```
89 #[inline]
90 #[must_use]
91 pub const fn empty(at: u32) -> Self {
92 Self { start: at, end: at }
93 }
94
95 /// Returns the start position (inclusive).
96 ///
97 /// # Examples
98 ///
99 /// ```
100 /// use span_lang::{BytePos, Span};
101 ///
102 /// assert_eq!(Span::new(3, 8).start(), BytePos::new(3));
103 /// ```
104 #[inline]
105 #[must_use]
106 pub const fn start(self) -> BytePos {
107 BytePos::new(self.start)
108 }
109
110 /// Returns the end position (exclusive).
111 ///
112 /// # Examples
113 ///
114 /// ```
115 /// use span_lang::{BytePos, Span};
116 ///
117 /// assert_eq!(Span::new(3, 8).end(), BytePos::new(8));
118 /// ```
119 #[inline]
120 #[must_use]
121 pub const fn end(self) -> BytePos {
122 BytePos::new(self.end)
123 }
124
125 /// Returns the length of the span in bytes.
126 ///
127 /// Always `end - start`, which the invariant guarantees is non-negative.
128 ///
129 /// # Examples
130 ///
131 /// ```
132 /// use span_lang::Span;
133 ///
134 /// assert_eq!(Span::new(4, 10).len(), 6);
135 /// assert_eq!(Span::empty(4).len(), 0);
136 /// ```
137 #[inline]
138 #[must_use]
139 pub const fn len(self) -> u32 {
140 self.end - self.start
141 }
142
143 /// Returns `true` if the span is zero-width (`start == end`).
144 ///
145 /// # Examples
146 ///
147 /// ```
148 /// use span_lang::Span;
149 ///
150 /// assert!(Span::empty(9).is_empty());
151 /// assert!(!Span::new(9, 12).is_empty());
152 /// ```
153 #[inline]
154 #[must_use]
155 pub const fn is_empty(self) -> bool {
156 self.start == self.end
157 }
158
159 /// Returns `true` if `pos` falls within the span (`start <= pos < end`).
160 ///
161 /// Membership is half-open to match the range: the `end` position is *not*
162 /// contained, and an empty span contains no position at all.
163 ///
164 /// # Examples
165 ///
166 /// ```
167 /// use span_lang::{BytePos, Span};
168 ///
169 /// let s = Span::new(4, 8);
170 /// assert!(s.contains(BytePos::new(4))); // start is included
171 /// assert!(s.contains(BytePos::new(7)));
172 /// assert!(!s.contains(BytePos::new(8))); // end is excluded
173 /// assert!(!Span::empty(4).contains(BytePos::new(4)));
174 /// ```
175 #[inline]
176 #[must_use]
177 pub const fn contains(self, pos: BytePos) -> bool {
178 let p = pos.to_u32();
179 self.start <= p && p < self.end
180 }
181
182 /// Returns the smallest span that covers both `self` and `other`.
183 ///
184 /// The result spans `min(starts)..max(ends)`. `merge` is commutative
185 /// (`a.merge(b) == b.merge(a)`) and associative
186 /// (`a.merge(b).merge(c) == a.merge(b.merge(c))`), so the order spans are
187 /// combined in never changes the result — useful when folding a node's span
188 /// over its children.
189 ///
190 /// # Examples
191 ///
192 /// ```
193 /// use span_lang::Span;
194 ///
195 /// let a = Span::new(4, 10);
196 /// let b = Span::new(8, 14);
197 /// assert_eq!(a.merge(b), Span::new(4, 14));
198 ///
199 /// // Disjoint spans merge to the range that encloses both.
200 /// assert_eq!(Span::new(0, 2).merge(Span::new(20, 24)), Span::new(0, 24));
201 /// ```
202 #[inline]
203 #[must_use]
204 pub const fn merge(self, other: Self) -> Self {
205 let start = if self.start < other.start {
206 self.start
207 } else {
208 other.start
209 };
210 let end = if self.end > other.end {
211 self.end
212 } else {
213 other.end
214 };
215 Self { start, end }
216 }
217}
218
219impl fmt::Display for Span {
220 /// Formats as `start..end`.
221 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
222 write!(f, "{}..{}", self.start, self.end)
223 }
224}
225
226#[cfg(feature = "serde")]
227impl serde::Serialize for Span {
228 fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
229 use serde::ser::SerializeStruct;
230 let mut state = serializer.serialize_struct("Span", 2)?;
231 state.serialize_field("start", &self.start)?;
232 state.serialize_field("end", &self.end)?;
233 state.end()
234 }
235}
236
237#[cfg(feature = "serde")]
238impl<'de> serde::Deserialize<'de> for Span {
239 /// Deserialises `{ start, end }` and routes it through [`Span::new`], so a
240 /// span read from an untrusted source upholds the `start <= end` invariant
241 /// exactly as a constructed one does — an inverted pair on the wire is
242 /// normalised, never accepted as-is.
243 fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
244 #[derive(serde::Deserialize)]
245 struct Raw {
246 start: u32,
247 end: u32,
248 }
249 let raw = Raw::deserialize(deserializer)?;
250 Ok(Span::new(raw.start, raw.end))
251 }
252}
253
254#[cfg(test)]
255mod tests {
256 use super::*;
257
258 #[test]
259 fn test_span_new_orders_inverted_arguments() {
260 assert_eq!(Span::new(9, 3), Span::new(3, 9));
261 assert!(Span::new(9, 3).start().to_u32() <= Span::new(9, 3).end().to_u32());
262 }
263
264 #[test]
265 fn test_span_len_and_is_empty_at_boundaries() {
266 assert_eq!(Span::empty(0).len(), 0);
267 assert!(Span::empty(0).is_empty());
268 assert_eq!(Span::new(0, 1).len(), 1);
269 assert!(!Span::new(0, 1).is_empty());
270 }
271
272 #[test]
273 fn test_span_contains_is_half_open() {
274 let s = Span::new(2, 5);
275 assert!(!s.contains(BytePos::new(1)));
276 assert!(s.contains(BytePos::new(2)));
277 assert!(s.contains(BytePos::new(4)));
278 assert!(!s.contains(BytePos::new(5)));
279 }
280
281 #[test]
282 fn test_span_merge_is_commutative_and_associative() {
283 let a = Span::new(4, 10);
284 let b = Span::new(8, 14);
285 let c = Span::new(1, 3);
286 assert_eq!(a.merge(b), b.merge(a));
287 assert_eq!(a.merge(b).merge(c), a.merge(b.merge(c)));
288 assert_eq!(a.merge(b).merge(c), Span::new(1, 14));
289 }
290
291 #[test]
292 fn test_span_orders_by_start_then_end() {
293 assert!(Span::new(0, 5) < Span::new(1, 2));
294 assert!(Span::new(0, 4) < Span::new(0, 5));
295 }
296
297 #[test]
298 fn test_span_display_uses_range_syntax() {
299 extern crate alloc;
300 use alloc::string::ToString;
301 assert_eq!(Span::new(3, 7).to_string(), "3..7");
302 }
303}