miden_debug_types/
span.rs

1use core::{
2    borrow::Borrow,
3    fmt,
4    hash::{Hash, Hasher},
5    ops::{Bound, Deref, DerefMut, Index, Range, RangeBounds},
6};
7
8use miden_crypto::utils::{
9    ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable,
10};
11#[cfg(feature = "serde")]
12use serde::{Deserialize, Serialize};
13
14use super::{ByteIndex, ByteOffset, SourceId};
15
16/// This trait should be implemented for any type that has an associated [SourceSpan].
17pub trait Spanned {
18    fn span(&self) -> SourceSpan;
19}
20
21impl Spanned for SourceSpan {
22    #[inline(always)]
23    fn span(&self) -> SourceSpan {
24        *self
25    }
26}
27
28impl<T: ?Sized + Spanned> Spanned for alloc::boxed::Box<T> {
29    fn span(&self) -> SourceSpan {
30        (**self).span()
31    }
32}
33
34impl<T: ?Sized + Spanned> Spanned for alloc::rc::Rc<T> {
35    fn span(&self) -> SourceSpan {
36        (**self).span()
37    }
38}
39
40impl<T: ?Sized + Spanned> Spanned for alloc::sync::Arc<T> {
41    fn span(&self) -> SourceSpan {
42        (**self).span()
43    }
44}
45
46// SPAN
47// ================================================================================================
48
49/// This type is used to wrap any `T` with a [SourceSpan], and is typically used when it is not
50/// convenient to add a [SourceSpan] to the type - most commonly because we don't control the type.
51///
52/// Note: `PartialEq` intentionally ignores the span, so the macro's equality oracle cannot detect
53/// span corruption; `span_roundtrip_preserves_span_and_value_separately` covers that gap.
54#[derive(Clone, Copy)]
55#[cfg_attr(
56    all(feature = "arbitrary", test),
57    miden_test_serialization_macros::serialization_test(types(u32))
58)]
59pub struct Span<T> {
60    span: SourceSpan,
61    spanned: T,
62}
63
64#[cfg(feature = "serde")]
65impl<T> Span<T> {
66    pub fn from_serde_spanned(source_id: SourceId, spanned: serde_spanned::Spanned<T>) -> Self {
67        let range = spanned.span();
68        let start = range.start as u32;
69        let end = range.end as u32;
70        let spanned = spanned.into_inner();
71        Self {
72            span: SourceSpan::new(source_id, start..end),
73            spanned,
74        }
75    }
76}
77
78#[cfg(feature = "serde")]
79impl<'de, T: Deserialize<'de>> Deserialize<'de> for Span<T> {
80    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
81    where
82        D: serde::Deserializer<'de>,
83    {
84        let spanned = T::deserialize(deserializer)?;
85        Ok(Self { span: SourceSpan::UNKNOWN, spanned })
86    }
87}
88
89#[cfg(feature = "serde")]
90impl<T: Serialize> Serialize for Span<T> {
91    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
92    where
93        S: serde::Serializer,
94    {
95        T::serialize(&self.spanned, serializer)
96    }
97}
98
99impl<T> Spanned for Span<T> {
100    fn span(&self) -> SourceSpan {
101        self.span
102    }
103}
104
105impl<T: Default> Default for Span<T> {
106    fn default() -> Self {
107        Self {
108            span: SourceSpan::UNKNOWN,
109            spanned: T::default(),
110        }
111    }
112}
113
114impl<T> Span<T> {
115    /// Creates a span for `spanned` with `span`.
116    #[inline]
117    pub fn new(span: impl Into<SourceSpan>, spanned: T) -> Self {
118        Self { span: span.into(), spanned }
119    }
120
121    /// Creates a span for `spanned` representing a single location, `offset`.
122    #[inline]
123    pub fn at(source_id: SourceId, offset: usize, spanned: T) -> Self {
124        let offset = u32::try_from(offset).expect("invalid source offset: too large");
125        Self {
126            span: SourceSpan::at(source_id, offset),
127            spanned,
128        }
129    }
130
131    /// Creates a [Span] from a value with an unknown/default location.
132    pub fn unknown(spanned: T) -> Self {
133        Self { span: Default::default(), spanned }
134    }
135
136    /// Consume this [Span] and get a new one with `span` as the underlying source span
137    #[inline]
138    pub fn with_span(mut self, span: SourceSpan) -> Self {
139        self.span = span;
140        self
141    }
142
143    /// Gets the associated [SourceSpan] for this spanned item.
144    #[inline(always)]
145    pub const fn span(&self) -> SourceSpan {
146        self.span
147    }
148
149    /// Gets a reference to the spanned item.
150    #[inline(always)]
151    pub const fn inner(&self) -> &T {
152        &self.spanned
153    }
154
155    /// Applies a transformation to the spanned value while retaining the same [SourceSpan].
156    #[inline]
157    pub fn map<U, F>(self, mut f: F) -> Span<U>
158    where
159        F: FnMut(T) -> U,
160    {
161        Span {
162            span: self.span,
163            spanned: f(self.spanned),
164        }
165    }
166
167    /// Like [`Option<T>::as_deref`], this constructs a [`Span<U>`] wrapping the result of
168    /// dereferencing the inner value of type `T` as a value of type `U`.
169    pub fn as_deref<U>(&self) -> Span<&U>
170    where
171        U: ?Sized,
172        T: Deref<Target = U>,
173    {
174        Span { span: self.span, spanned: &*self.spanned }
175    }
176
177    /// Gets a new [Span] that borrows the inner value.
178    pub fn as_ref(&self) -> Span<&T> {
179        Span { span: self.span, spanned: &self.spanned }
180    }
181
182    /// Manually set the source id for the span of this item
183    ///
184    /// See also [SourceSpan::set_source_id].
185    pub fn set_source_id(&mut self, id: SourceId) {
186        self.span.set_source_id(id);
187    }
188
189    /// Shifts the span right by `count` units
190    #[inline]
191    pub fn shift(&mut self, count: ByteOffset) {
192        self.span.start += count;
193        self.span.end += count;
194    }
195
196    /// Extends the end of the span by `count` units.
197    #[inline]
198    pub fn extend(&mut self, count: ByteOffset) {
199        self.span.end += count;
200    }
201
202    /// Consumes this span, returning the component parts, i.e. the [SourceSpan] and value of type
203    /// `T`.
204    #[inline]
205    pub fn into_parts(self) -> (SourceSpan, T) {
206        (self.span, self.spanned)
207    }
208
209    /// Unwraps the spanned value of type `T`.
210    #[inline]
211    pub fn into_inner(self) -> T {
212        self.spanned
213    }
214}
215
216impl<T> Borrow<T> for Span<T> {
217    fn borrow(&self) -> &T {
218        &self.spanned
219    }
220}
221
222impl<T: Borrow<str>> Borrow<str> for Span<T> {
223    fn borrow(&self) -> &str {
224        self.spanned.borrow()
225    }
226}
227
228impl<U, T: Borrow<[U]>> Borrow<[U]> for Span<T> {
229    fn borrow(&self) -> &[U] {
230        self.spanned.borrow()
231    }
232}
233
234impl<T> Deref for Span<T> {
235    type Target = T;
236
237    #[inline(always)]
238    fn deref(&self) -> &Self::Target {
239        &self.spanned
240    }
241}
242
243impl<T> DerefMut for Span<T> {
244    #[inline(always)]
245    fn deref_mut(&mut self) -> &mut Self::Target {
246        &mut self.spanned
247    }
248}
249
250impl<T: ?Sized, U: AsRef<T>> AsRef<T> for Span<U> {
251    fn as_ref(&self) -> &T {
252        self.spanned.as_ref()
253    }
254}
255
256impl<T: ?Sized, U: AsMut<T>> AsMut<T> for Span<U> {
257    fn as_mut(&mut self) -> &mut T {
258        self.spanned.as_mut()
259    }
260}
261
262impl<T: fmt::Debug> fmt::Debug for Span<T> {
263    #[inline]
264    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
265        fmt::Debug::fmt(&self.spanned, f)
266    }
267}
268
269impl<T: fmt::Display> fmt::Display for Span<T> {
270    #[inline]
271    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
272        fmt::Display::fmt(&self.spanned, f)
273    }
274}
275
276impl<T: miden_formatting::prettier::PrettyPrint> miden_formatting::prettier::PrettyPrint
277    for Span<T>
278{
279    fn render(&self) -> miden_formatting::prettier::Document {
280        self.spanned.render()
281    }
282}
283
284impl<T: Eq> Eq for Span<T> {}
285
286impl<T: PartialEq> PartialEq for Span<T> {
287    #[inline]
288    fn eq(&self, other: &Self) -> bool {
289        self.spanned.eq(&other.spanned)
290    }
291}
292
293impl<T: PartialEq> PartialEq<T> for Span<T> {
294    #[inline]
295    fn eq(&self, other: &T) -> bool {
296        self.spanned.eq(other)
297    }
298}
299
300impl<T: Ord> Ord for Span<T> {
301    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
302        self.spanned.cmp(&other.spanned)
303    }
304}
305
306impl<T: PartialOrd> PartialOrd for Span<T> {
307    #[inline]
308    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
309        self.spanned.partial_cmp(&other.spanned)
310    }
311}
312
313impl<T: Hash> Hash for Span<T> {
314    fn hash<H: Hasher>(&self, state: &mut H) {
315        self.spanned.hash(state);
316    }
317}
318
319impl<T: Serializable> Span<T> {
320    pub fn write_into_with_options<W: ByteWriter>(&self, target: &mut W, debug: bool) {
321        if debug {
322            self.span.write_into(target);
323        }
324        self.spanned.write_into(target);
325    }
326}
327
328impl<T: Serializable> Serializable for Span<T> {
329    fn write_into<W: ByteWriter>(&self, target: &mut W) {
330        self.span.write_into(target);
331        self.spanned.write_into(target);
332    }
333}
334
335impl<T: Deserializable> Span<T> {
336    pub fn read_from_with_options<R: ByteReader>(
337        source: &mut R,
338        debug: bool,
339    ) -> Result<Self, DeserializationError> {
340        let span = if debug {
341            SourceSpan::read_from(source)?
342        } else {
343            SourceSpan::default()
344        };
345        let spanned = T::read_from(source)?;
346        Ok(Self { span, spanned })
347    }
348}
349
350impl<T: Deserializable> Deserializable for Span<T> {
351    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
352        let span = SourceSpan::read_from(source)?;
353        let spanned = T::read_from(source)?;
354        Ok(Self { span, spanned })
355    }
356}
357
358// SOURCE SPAN
359// ================================================================================================
360
361/// This represents a span of bytes in a Miden Assembly source file.
362///
363/// It is compact, using only 8 bytes to represent the full span. This does, however, come at the
364/// tradeoff of only supporting source files of up to 2^32 bytes.
365///
366/// This type is produced by the lexer and carried through parsing. It can be converted into a
367/// line/column range as well, if needed.
368///
369/// This representation is more convenient to produce, and allows showing source spans in error
370/// messages, whereas line/column information is useful at a glance in debug output, it is harder
371/// to produce nice errors with it compared to this representation.
372#[derive(Debug, Default, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
373#[cfg_attr(feature = "serde", derive(Serialize))]
374#[cfg_attr(
375    all(feature = "arbitrary", test),
376    miden_test_serialization_macros::serialization_test
377)]
378pub struct SourceSpan {
379    #[cfg_attr(feature = "serde", serde(default, skip_serializing_if = "SourceId::is_unknown"))]
380    source_id: SourceId,
381    start: ByteIndex,
382    end: ByteIndex,
383}
384
385#[derive(Debug, thiserror::Error)]
386#[error("invalid byte index range {start}..{end}: expected start <= end <= u32::MAX")]
387pub struct InvalidByteIndexRange {
388    start: usize,
389    end: usize,
390}
391
392#[cfg(feature = "serde")]
393impl<'de> Deserialize<'de> for SourceSpan {
394    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
395        #[derive(Deserialize)]
396        #[serde(rename = "SourceSpan")]
397        struct RawSourceSpan {
398            #[serde(default)]
399            source_id: SourceId,
400            start: ByteIndex,
401            end: ByteIndex,
402        }
403
404        let RawSourceSpan { source_id, start, end } = RawSourceSpan::deserialize(deserializer)?;
405        if start > end {
406            return Err(serde::de::Error::custom(alloc::format!(
407                "source span start {} exceeds end {}",
408                start.to_u32(),
409                end.to_u32()
410            )));
411        }
412        Ok(Self { source_id, start, end })
413    }
414}
415
416impl SourceSpan {
417    /// A sentinel [SourceSpan] that indicates the span is unknown/invalid
418    pub const UNKNOWN: Self = Self {
419        source_id: SourceId::UNKNOWN,
420        start: ByteIndex::new(0),
421        end: ByteIndex::new(0),
422    };
423
424    /// A sentinel [SourceSpan] that indicates compiler-generated/synthetic code
425    ///
426    /// This is used to distinguish between:
427    /// - UNKNOWN: debug info missing or failed to parse from DWARF
428    /// - SYNTHETIC: compiler-generated code that doesn't correspond to any user source
429    pub const SYNTHETIC: Self = Self {
430        source_id: SourceId::UNKNOWN,
431        start: ByteIndex::new(u32::MAX),
432        end: ByteIndex::new(u32::MAX),
433    };
434
435    /// Creates a new [SourceSpan] from the given range.
436    ///
437    /// # Panics
438    ///
439    /// Panics if the start of the range exceeds its end.
440    pub fn new<B>(source_id: SourceId, range: Range<B>) -> Self
441    where
442        B: Into<ByteIndex>,
443    {
444        let start = range.start.into();
445        let end = range.end.into();
446        assert!(
447            start <= end,
448            "source span start {} exceeds end {}",
449            start.to_u32(),
450            end.to_u32()
451        );
452        Self { source_id, start, end }
453    }
454
455    /// Creates a new [SourceSpan] for a specific offset.
456    pub fn at(source_id: SourceId, offset: impl Into<ByteIndex>) -> Self {
457        let offset = offset.into();
458        Self { source_id, start: offset, end: offset }
459    }
460
461    /// Try to create a new [SourceSpan] from the given range with `usize` bounds.
462    ///
463    /// Returns an error if the bounds are reversed or exceed `u32::MAX`.
464    pub fn try_from_range(
465        source_id: SourceId,
466        range: Range<usize>,
467    ) -> Result<Self, InvalidByteIndexRange> {
468        const MAX: usize = u32::MAX as usize;
469        if range.start > range.end || range.start > MAX || range.end > MAX {
470            return Err(InvalidByteIndexRange { start: range.start, end: range.end });
471        }
472
473        Ok(SourceSpan {
474            source_id,
475            start: ByteIndex::from(range.start as u32),
476            end: ByteIndex::from(range.end as u32),
477        })
478    }
479
480    /// Returns `true` if this [SourceSpan] represents the unknown span
481    pub const fn is_unknown(&self) -> bool {
482        self.source_id.is_unknown() && self.start.to_u32() == 0 && self.end.to_u32() == 0
483    }
484
485    /// Returns `true` if this [SourceSpan] represents synthetic/compiler-generated code
486    pub const fn is_synthetic(&self) -> bool {
487        self.source_id.is_unknown()
488            && self.start.to_u32() == u32::MAX
489            && self.end.to_u32() == u32::MAX
490    }
491
492    /// Get the [SourceId] associated with this source span
493    #[inline(always)]
494    pub fn source_id(&self) -> SourceId {
495        self.source_id
496    }
497
498    /// Manually set the [SourceId] associated with this source span
499    ///
500    /// This is useful in cases where the range of the span is known, but the source id itself
501    /// is not available yet, due to scope or some other limitation. In such cases you might wish
502    /// to visit parsed objects once the source id is available, and update all of their spans
503    /// accordingly.
504    pub fn set_source_id(&mut self, id: SourceId) {
505        self.source_id = id;
506    }
507
508    /// Gets the offset in bytes corresponding to the start of this span (inclusive).
509    #[inline(always)]
510    pub fn start(&self) -> ByteIndex {
511        self.start
512    }
513
514    /// Gets the offset in bytes corresponding to the end of this span (exclusive).
515    #[inline(always)]
516    pub fn end(&self) -> ByteIndex {
517        self.end
518    }
519
520    /// Gets the length of this span in bytes.
521    #[inline(always)]
522    pub fn len(&self) -> usize {
523        self.end.to_usize() - self.start.to_usize()
524    }
525
526    /// Returns true if this span is empty.
527    pub fn is_empty(&self) -> bool {
528        self.len() == 0
529    }
530
531    /// Converts this span into a [`Range<u32>`].
532    #[inline]
533    pub fn into_range(self) -> Range<u32> {
534        self.start.to_u32()..self.end.to_u32()
535    }
536
537    /// Converts this span into a [`Range<usize>`].
538    #[inline]
539    pub fn into_slice_index(self) -> Range<usize> {
540        self.start.to_usize()..self.end.to_usize()
541    }
542}
543
544impl From<SourceSpan> for miette::SourceSpan {
545    fn from(span: SourceSpan) -> Self {
546        Self::new(miette::SourceOffset::from(span.start().to_usize()), span.len())
547    }
548}
549
550impl Serializable for SourceSpan {
551    fn write_into<W: ByteWriter>(&self, target: &mut W) {
552        target.write_u32(self.source_id.to_u32());
553        target.write_u32(self.start.into());
554        target.write_u32(self.end.into())
555    }
556}
557
558impl Deserializable for SourceSpan {
559    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
560        let source_id = SourceId::new_unchecked(source.read_u32()?);
561        let start = ByteIndex::from(source.read_u32()?);
562        let end = ByteIndex::from(source.read_u32()?);
563        if start > end {
564            return Err(DeserializationError::InvalidValue(alloc::format!(
565                "source span start {} exceeds end {}",
566                start.to_u32(),
567                end.to_u32()
568            )));
569        }
570        Ok(Self { source_id, start, end })
571    }
572}
573
574impl From<SourceSpan> for Range<u32> {
575    #[inline(always)]
576    fn from(span: SourceSpan) -> Self {
577        span.into_range()
578    }
579}
580
581impl From<SourceSpan> for Range<usize> {
582    #[inline(always)]
583    fn from(span: SourceSpan) -> Self {
584        span.into_slice_index()
585    }
586}
587
588impl From<Range<u32>> for SourceSpan {
589    #[inline]
590    fn from(range: Range<u32>) -> Self {
591        Self::new(SourceId::UNKNOWN, range)
592    }
593}
594
595impl From<Range<ByteIndex>> for SourceSpan {
596    #[inline]
597    fn from(range: Range<ByteIndex>) -> Self {
598        Self::new(SourceId::UNKNOWN, range)
599    }
600}
601
602impl Index<SourceSpan> for [u8] {
603    type Output = [u8];
604
605    #[inline]
606    fn index(&self, index: SourceSpan) -> &Self::Output {
607        &self[index.start().to_usize()..index.end().to_usize()]
608    }
609}
610
611impl RangeBounds<ByteIndex> for SourceSpan {
612    #[inline(always)]
613    fn start_bound(&self) -> Bound<&ByteIndex> {
614        Bound::Included(&self.start)
615    }
616
617    #[inline(always)]
618    fn end_bound(&self) -> Bound<&ByteIndex> {
619        Bound::Excluded(&self.end)
620    }
621}
622
623// ARBITRARY (proptest)
624// ================================================================================================
625
626#[cfg(feature = "arbitrary")]
627mod arbitrary {
628    use proptest::prelude::*;
629
630    use super::{SourceId, SourceSpan, Span};
631
632    impl Arbitrary for SourceSpan {
633        type Parameters = ();
634        type Strategy = BoxedStrategy<Self>;
635
636        fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
637            // The type invariant is start <= end (`len()` computes unsigned end - start), so the
638            // generator produces ordered spans only.
639            (any::<SourceId>(), any::<u32>(), any::<u32>())
640                .prop_map(|(source_id, a, b)| {
641                    let (start, end) = if a <= b { (a, b) } else { (b, a) };
642                    SourceSpan::new(source_id, start..end)
643                })
644                .boxed()
645        }
646    }
647
648    impl<T> Arbitrary for Span<T>
649    where
650        T: Arbitrary,
651        T::Strategy: 'static,
652    {
653        type Parameters = ();
654        type Strategy = BoxedStrategy<Self>;
655
656        fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
657            (any::<SourceSpan>(), any::<T>())
658                .prop_map(|(span, spanned)| Span::new(span, spanned))
659                .boxed()
660        }
661    }
662
663    proptest! {
664        /// `Span<T>`'s `PartialEq` intentionally ignores the span, so the macro's equality oracle
665        /// cannot detect span corruption in transit. This property compares the span fields and
666        /// the inner value separately, which is the actual wire contract.
667        #[test]
668        fn span_roundtrip_preserves_span_and_value_separately(
669            (source_id, start, end, value) in
670                (any::<u32>(), any::<u32>(), any::<u32>(), any::<u32>()),
671        ) {
672            use miden_crypto::utils::{Deserializable, Serializable};
673
674            let (start, end) = (start.min(end), start.max(end));
675            let span = SourceSpan::new(SourceId::from(source_id), start..end);
676            let wrapped = Span::new(span, value);
677
678            let bytes = wrapped.to_bytes();
679            let round_trip = Span::<u32>::read_from_bytes(&bytes).unwrap();
680
681            assert_eq!(round_trip.span(), span);
682            assert_eq!(round_trip.inner(), &value);
683        }
684    }
685}
686
687#[cfg(test)]
688mod tests {
689    use miden_crypto::utils::Deserializable;
690
691    use super::*;
692
693    /// Decoding preserves the ordered bounds required by `len()`.
694    #[test]
695    fn wire_decoder_rejects_reversed_bounds() {
696        let mut bytes = alloc::vec::Vec::new();
697        bytes.write_u32(0); // source_id
698        bytes.write_u32(5); // start
699        bytes.write_u32(3); // end (reversed)
700
701        assert_eq!(
702            SourceSpan::read_from_bytes(&bytes),
703            Err(DeserializationError::InvalidValue("source span start 5 exceeds end 3".into()))
704        );
705    }
706}
miden_debug_types/span.rs

miden_debug_types/
span.rs
