diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/source.rs | 3 | ||||
| -rw-r--r-- | src/syntax/mod.rs | 44 | ||||
| -rw-r--r-- | src/syntax/span.rs | 39 |
3 files changed, 52 insertions, 34 deletions
diff --git a/src/source.rs b/src/source.rs index 61abcd92..507e4d20 100644 --- a/src/source.rs +++ b/src/source.rs @@ -141,7 +141,8 @@ impl SourceStore { self.sources[id.0 as usize].edit(replace, with) } - /// Map a span that points into this source store to a byte range. + /// Map a span that points into a [file](SourceFile::range) stored in this + /// source store to a byte range. /// /// Panics if the span does not point into this source store. pub fn range(&self, span: Span) -> Range<usize> { diff --git a/src/syntax/mod.rs b/src/syntax/mod.rs index 92d00878..4a163d78 100644 --- a/src/syntax/mod.rs +++ b/src/syntax/mod.rs @@ -122,7 +122,7 @@ impl SyntaxNode { } } - /// Set a synthetic node id for the node and all its descendants. + /// Set a synthetic span for the node and all its descendants. pub fn synthesize(&mut self, span: Span) { match self { Self::Inner(inner) => Arc::make_mut(inner).synthesize(span), @@ -258,7 +258,7 @@ impl InnerNode { self.children.iter() } - /// Set a synthetic node id for the node and all its descendants. + /// Set a synthetic span for the node and all its descendants. pub fn synthesize(&mut self, span: Span) { self.data.synthesize(span); for child in &mut self.children { @@ -266,13 +266,15 @@ impl InnerNode { } } - /// Assign spans to this subtree or some a range of children. + /// Assign span numbers `within` an interval to this node's subtree or just + /// a `range` of its children. pub fn numberize( &mut self, id: SourceId, range: Option<Range<usize>>, within: Range<u64>, ) -> NumberingResult { + // Determine how many nodes we will number. let descendants = match &range { Some(range) if range.is_empty() => return Ok(()), Some(range) => self.children[range.clone()] @@ -282,6 +284,9 @@ impl InnerNode { None => self.descendants, }; + // Determine the distance between two neighbouring assigned numbers. If + // possible, we try to fit all numbers into the left half of `within` + // so that there is space for future insertions. let space = within.end - within.start; let mut stride = space / (2 * descendants as u64); if stride == 0 { @@ -291,6 +296,7 @@ impl InnerNode { } } + // Number this node itself. let mut start = within.start; if range.is_none() { let end = start + stride; @@ -299,6 +305,7 @@ impl InnerNode { start = end; } + // Number the children. let len = self.children.len(); for child in &mut self.children[range.unwrap_or(0 .. len)] { let end = start + child.descendants() as u64 * stride; @@ -309,7 +316,7 @@ impl InnerNode { Ok(()) } - /// The maximum assigned number in this subtree. + /// The upper bound of assigned numbers in this subtree. pub fn upper(&self) -> u64 { self.upper } @@ -387,39 +394,44 @@ impl InnerNode { self.children.splice(range.clone(), replacement); range.end = range.start + replacement_count; - // Renumber the new children. Retries until it works taking + // Renumber the new children. Retries until it works, taking // exponentially more children into account. - let max_left = range.start; - let max_right = self.children.len() - range.end; let mut left = 0; let mut right = 0; + let max_left = range.start; + let max_right = self.children.len() - range.end; loop { let renumber = range.start - left .. range.end + right; - // The minimum assignable number is the upper bound of the node - // right before the to-be-renumbered children (or the number after - // this inner node's span if renumbering starts at the first child). + // The minimum assignable number is either + // - the upper bound of the node right before the to-be-renumbered + // children, + // - or this inner node's span number plus one if renumbering starts + // at the first child. let start_number = renumber .start .checked_sub(1) .and_then(|i| self.children.get(i)) .map_or(self.span().number() + 1, |child| child.upper()); - // The upper bound of the is the span of the first child after the to-be-renumbered children - // or this node's upper bound. + // The upper bound for renumbering is either + // - the span number of the first child after the to-be-renumbered + // children, + // - or this node's upper bound if renumbering ends behind the last + // child. let end_number = self .children .get(renumber.end) .map_or(self.upper(), |next| next.span().number()); - // Try to renumber within the number range. + // Try to renumber. let within = start_number .. end_number; let id = self.span().source(); if self.numberize(id, Some(renumber), within).is_ok() { return Ok(()); } - // Doesn't even work with all children, so we give up. + // If it didn't even work with all children, we give up. if left == max_left && right == max_right { return Err(Unnumberable); } @@ -430,8 +442,8 @@ impl InnerNode { } } - /// Update the length of this node given the old and new length of - /// replaced children. + /// Update the this node given after changes were made to one of its + /// children. pub(crate) fn update_parent( &mut self, prev_len: usize, diff --git a/src/syntax/span.rs b/src/syntax/span.rs index d58ee326..5dcd8fc1 100644 --- a/src/syntax/span.rs +++ b/src/syntax/span.rs @@ -42,42 +42,47 @@ impl<T: Debug> Debug for Spanned<T> { /// A unique identifier for a syntax node. /// /// This is used throughout the compiler to track which source section an error -/// or element stems from. Can be mapped back to a source id + byte range for -/// user facing display. +/// or element stems from. Can be [mapped back](crate::source::SourceStore::range) +/// to a source id + byte range for user facing display. /// -/// Node ids are ordered in the tree to enable quickly finding the node with +/// Span ids are ordered in the tree to enable quickly finding the node with /// some id: /// - The id of a parent is always smaller than the ids of any of its children. /// - The id of a node is always greater than any id in the subtrees of any left -/// sibling and smaller than any id the subtrees of any right sibling. +/// sibling and smaller than any id in the subtrees of any right sibling. /// -/// Node ids stay mostly stable, even for nodes behind an insertion. This is not -/// true for simple spans/ranges as they shift. Node ids can be used as inputs -/// to memoized functions without hurting cache performance when text is -/// inserted somewhere in the document other than the end. -#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)] +/// The internal ids of spans stay mostly stable, even for nodes behind an +/// insertion. This is not true for simple ranges as they shift. Spans can be +/// used as inputs to memoized functions without hurting cache performance when +/// text is inserted somewhere in the document other than the end. +/// +/// This type takes 8 bytes and is null-optimized (i.e. `Option<Span>` also +/// takes 8 bytes). +#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)] pub struct Span(NonZeroU64); impl Span { - // Number of bits for and minimum and maximum numbers assigned to nodes. + // Number of bits for and minimum and maximum numbers assignable to spans. const BITS: usize = 48; const DETACHED: u64 = 1; const MIN: u64 = 2; const MAX: u64 = (1 << Self::BITS) - 1; - // The root numbering range. + /// The full range of numbers available to spans. pub const FULL: Range<u64> = Self::MIN .. Self::MAX + 1; /// Create a new span from a source id and a unique number. - pub fn new(id: SourceId, number: u64) -> Self { - assert!(number >= Self::MIN && number <= Self::MAX, "{number}"); + /// + /// Panics if the `number` is not contained in `FULL`. + pub const fn new(id: SourceId, number: u64) -> Self { + assert!(number >= Self::MIN && number <= Self::MAX); let bits = ((id.into_raw() as u64) << Self::BITS) | number; - Self(convert(bits)) + Self(to_non_zero(bits)) } - /// A node that does not belong to any source file. + /// A span that does not point into any source file. pub const fn detached() -> Self { - Self(convert(Self::DETACHED)) + Self(to_non_zero(Self::DETACHED)) } /// The id of the source file the span points into. @@ -92,7 +97,7 @@ impl Span { } /// Convert to a non zero u64. -const fn convert(v: u64) -> NonZeroU64 { +const fn to_non_zero(v: u64) -> NonZeroU64 { match NonZeroU64::new(v) { Some(v) => v, None => unreachable!(), |