use crate::{EditorLexeme, EditorLexemeKind, ParseControl, ParseControlResult, SourceSpan};
use std::ops::Range;
const CONTROLLED_EDIT_REBUILD_CHECKPOINT_BYTES: usize = 4 * 1024;
const CONTROLLED_EDIT_REBUILD_CHECKPOINT_ITEMS: usize = 128;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(super) enum ReplacementMapping {
ExactBytes,
Boundaries,
}
#[derive(Debug, Clone)]
pub(super) struct SourceEdit {
range: Range<usize>,
replacement: String,
mapping: ReplacementMapping,
}
impl SourceEdit {
pub(super) fn delete(range: Range<usize>) -> Self {
Self {
range,
replacement: String::new(),
mapping: ReplacementMapping::Boundaries,
}
}
pub(super) fn replace(
range: Range<usize>,
replacement: impl Into<String>,
mapping: ReplacementMapping,
) -> Self {
Self {
range,
replacement: replacement.into(),
mapping,
}
}
}
#[derive(Debug, Clone)]
pub struct PreprocessedSource {
text: String,
edit_map: SourceEditMap,
global_lexemes: Vec<EditorLexeme>,
global_directive_prefixes: Vec<String>,
recovered_incomplete_directive: bool,
}
impl PreprocessedSource {
pub fn new(source: &str) -> Self {
Self::new_controlled(source, &ParseControl::new())
.expect("a private parse control cannot be cancelled")
}
pub(super) fn new_controlled(source: &str, control: &ParseControl) -> ParseControlResult<Self> {
control.checkpoint()?;
let mut text = String::with_capacity(source.len());
let mut chunk_start = 0usize;
while source.len().saturating_sub(chunk_start) >= CONTROLLED_EDIT_REBUILD_CHECKPOINT_BYTES {
let mut chunk_end = chunk_start + CONTROLLED_EDIT_REBUILD_CHECKPOINT_BYTES;
while !source.is_char_boundary(chunk_end) {
chunk_end += 1;
}
text.push_str(&source[chunk_start..chunk_end]);
control.checkpoint()?;
chunk_start = chunk_end;
}
text.push_str(&source[chunk_start..]);
control.checkpoint()?;
Ok(Self {
text,
edit_map: SourceEditMap::identity(source.len()),
global_lexemes: Vec::new(),
global_directive_prefixes: Vec::new(),
recovered_incomplete_directive: false,
})
}
pub fn text(&self) -> &str {
&self.text
}
pub fn try_map_span(&self, span: SourceSpan) -> Option<SourceSpan> {
if !self.text.is_char_boundary(span.start) || !self.text.is_char_boundary(span.end) {
return None;
}
self.edit_map.try_map_span(span)
}
pub(crate) fn global_lexemes(&self) -> &[EditorLexeme] {
&self.global_lexemes
}
pub(crate) fn global_directive_prefixes(&self) -> &[String] {
&self.global_directive_prefixes
}
pub(crate) const fn recovered_incomplete_directive(&self) -> bool {
self.recovered_incomplete_directive
}
pub(super) fn mark_recovered_incomplete_directive(&mut self) {
self.recovered_incomplete_directive = true;
}
pub(super) fn record_global_directive_prefix(&mut self, prefix: String) {
if !self.global_directive_prefixes.contains(&prefix) {
self.global_directive_prefixes.push(prefix);
}
}
pub(super) fn record_global_lexeme(&mut self, kind: EditorLexemeKind, span: SourceSpan) {
let Some(span) = self.try_map_span(span) else {
return;
};
if span.start < span.end {
self.global_lexemes.push(EditorLexeme::global(kind, span));
}
}
pub fn into_text(self) -> String {
self.text
}
pub(super) fn apply_edits(
&mut self,
edits: Vec<SourceEdit>,
control: &ParseControl,
) -> ParseControlResult<()> {
let mut checkpoints = ControlledEditRebuildCheckpoints::new(control)?;
if edits.is_empty() {
return Ok(());
}
assert!(
edits_are_sorted_controlled(&edits, &mut checkpoints)?,
"source edits must be sorted by range"
);
let (replacement_bytes, removed_bytes) =
assert_valid_edits_controlled(&self.text, &edits, &mut checkpoints)?;
let old_text = &self.text;
let old_map = &self.edit_map;
let mut text = String::with_capacity(
old_text
.len()
.saturating_sub(removed_bytes)
.saturating_add(replacement_bytes),
);
let mut builder = EditMapBuilder::new(old_map.original_len);
let mut cursor = 0usize;
for edit in edits {
checkpoints.processed_item()?;
checkpoints.push_str(&mut text, &old_text[cursor..edit.range.start])?;
builder.copy_from(old_map, cursor..edit.range.start, &mut checkpoints)?;
if edit.replacement.is_empty() {
builder.delete_from(old_map, edit.range.clone(), &mut checkpoints)?;
} else {
checkpoints.push_str(&mut text, &edit.replacement)?;
builder.replace_from(
old_map,
edit.range.clone(),
edit.replacement.len(),
edit.mapping,
&mut checkpoints,
)?;
}
cursor = edit.range.end;
}
checkpoints.push_str(&mut text, &old_text[cursor..])?;
builder.copy_from(old_map, cursor..old_text.len(), &mut checkpoints)?;
let edit_map = builder.finish(text.len(), &mut checkpoints)?;
#[cfg(debug_assertions)]
{
let well_formed = edit_map.is_well_formed_controlled(&mut checkpoints)?;
debug_assert!(well_formed);
}
checkpoints.finish()?;
self.text = text;
self.edit_map = edit_map;
Ok(())
}
#[cfg(test)]
fn apply_edits_uncontrolled(&mut self, edits: Vec<SourceEdit>) {
self.apply_edits(edits, &ParseControl::new())
.expect("a private parse control cannot be cancelled");
}
}
struct ControlledEditRebuildCheckpoints<'a> {
control: &'a ParseControl,
bytes_since_checkpoint: usize,
items_since_checkpoint: usize,
}
impl<'a> ControlledEditRebuildCheckpoints<'a> {
fn new(control: &'a ParseControl) -> ParseControlResult<Self> {
control.checkpoint()?;
Ok(Self {
control,
bytes_since_checkpoint: 0,
items_since_checkpoint: 0,
})
}
fn push_str(&mut self, output: &mut String, value: &str) -> ParseControlResult<()> {
let mut start = 0usize;
while start < value.len() {
let remaining_budget = CONTROLLED_EDIT_REBUILD_CHECKPOINT_BYTES
.saturating_sub(self.bytes_since_checkpoint);
if remaining_budget == 0 {
self.checkpoint()?;
continue;
}
let mut end = start.saturating_add(remaining_budget).min(value.len());
while end > start && !value.is_char_boundary(end) {
end -= 1;
}
if end == start {
self.checkpoint()?;
continue;
}
output.push_str(&value[start..end]);
self.bytes_since_checkpoint += end - start;
start = end;
if self.bytes_since_checkpoint == CONTROLLED_EDIT_REBUILD_CHECKPOINT_BYTES {
self.checkpoint()?;
}
}
Ok(())
}
fn processed_item(&mut self) -> ParseControlResult<()> {
self.items_since_checkpoint += 1;
if self.items_since_checkpoint == CONTROLLED_EDIT_REBUILD_CHECKPOINT_ITEMS {
self.checkpoint()?;
}
Ok(())
}
fn checkpoint(&mut self) -> ParseControlResult<()> {
self.control.checkpoint()?;
self.bytes_since_checkpoint = 0;
self.items_since_checkpoint = 0;
Ok(())
}
fn finish(&self) -> ParseControlResult<()> {
self.control.checkpoint()
}
}
#[derive(Debug, Clone)]
struct SourceEditMap {
original_len: usize,
output_len: usize,
segments: Vec<EditMapSegment>,
gaps: Vec<EditMapGap>,
unmapped_output_ranges: Vec<Range<usize>>,
#[cfg(test)]
scan_stats: EditMapScanStats,
}
impl SourceEditMap {
fn identity(source_len: usize) -> Self {
let segments = (source_len > 0)
.then_some(EditMapSegment {
output: 0..source_len,
original: 0..source_len,
mapping: SegmentMapping::ExactBytes,
})
.into_iter()
.collect();
Self {
original_len: source_len,
output_len: source_len,
segments,
gaps: Vec::new(),
unmapped_output_ranges: Vec::new(),
#[cfg(test)]
scan_stats: EditMapScanStats::default(),
}
}
fn try_map_span(&self, span: SourceSpan) -> Option<SourceSpan> {
if span.start > span.end || span.end > self.output_len {
return None;
}
if self.has_unmapped_overlap(span.start, span.end)
|| (span.start < span.end && self.has_gap_inside(span.start, span.end))
{
return None;
}
let start = self.original_at_start(span.start)?;
let end = if span.start == span.end {
start
} else {
self.original_at_end(span.end)?
};
(start <= end).then(|| SourceSpan::new(start, end))
}
fn original_at_start(&self, offset: usize) -> Option<usize> {
if offset > self.output_len {
return None;
}
if let Some(gap) = self.gap_at(offset) {
return Some(gap.original_right);
}
if offset == self.output_len {
return match self.segments.last() {
Some(segment) => segment.original_at_end(offset),
None => Some(self.original_len),
};
}
self.segment_to_right(offset)?.original_at_start(offset)
}
fn original_at_end(&self, offset: usize) -> Option<usize> {
if offset > self.output_len {
return None;
}
if let Some(gap) = self.gap_at(offset) {
return Some(gap.original_left);
}
if offset == 0 {
return match self.segments.first() {
Some(segment) => segment.original_at_start(offset),
None => Some(0),
};
}
self.segment_to_left(offset)?.original_at_end(offset)
}
fn segment_to_right(&self, offset: usize) -> Option<&EditMapSegment> {
let index = self
.segments
.partition_point(|segment| segment.output.end <= offset);
self.segments
.get(index)
.filter(|segment| segment.output.start <= offset && offset < segment.output.end)
}
fn segment_to_left(&self, offset: usize) -> Option<&EditMapSegment> {
let index = self
.segments
.partition_point(|segment| segment.output.start < offset)
.checked_sub(1)?;
self.segments
.get(index)
.filter(|segment| segment.output.start < offset && offset <= segment.output.end)
}
fn gap_at(&self, offset: usize) -> Option<&EditMapGap> {
self.gaps
.binary_search_by_key(&offset, |gap| gap.output_offset)
.ok()
.and_then(|index| self.gaps.get(index))
}
fn has_gap_inside(&self, start: usize, end: usize) -> bool {
let first = self.gaps.partition_point(|gap| gap.output_offset <= start);
self.gaps
.get(first)
.is_some_and(|gap| gap.output_offset < end)
}
fn has_unmapped_overlap(&self, start: usize, end: usize) -> bool {
let first = self
.unmapped_output_ranges
.partition_point(|range| range.end <= start);
self.unmapped_output_ranges.get(first).is_some_and(|range| {
if start == end {
range.start < start && start < range.end
} else {
range.start < end && start < range.end
}
})
}
#[cfg(test)]
fn unmapped_ranges_match_segments(&self) -> bool {
self.unmapped_output_ranges.iter().eq(self
.segments
.iter()
.filter(|segment| segment.mapping == SegmentMapping::Unmapped)
.map(|segment| &segment.output))
}
#[cfg(test)]
fn is_well_formed(&self) -> bool {
let control = ParseControl::new();
let mut checkpoints = ControlledEditRebuildCheckpoints::new(&control)
.expect("a private parse control cannot be cancelled");
self.is_well_formed_controlled(&mut checkpoints)
.expect("a private parse control cannot be cancelled")
}
#[cfg(any(test, debug_assertions))]
fn is_well_formed_controlled(
&self,
checkpoints: &mut ControlledEditRebuildCheckpoints<'_>,
) -> ParseControlResult<bool> {
let mut previous_segment: Option<&EditMapSegment> = None;
let mut unmapped_index = 0usize;
for segment in &self.segments {
checkpoints.processed_item()?;
if segment.output.start >= segment.output.end {
return Ok(false);
}
if let Some(previous) = previous_segment
&& (previous.output.end > segment.output.start
|| previous.original.end > segment.original.start)
{
return Ok(false);
}
if segment.mapping == SegmentMapping::Unmapped {
if self.unmapped_output_ranges.get(unmapped_index) != Some(&segment.output) {
return Ok(false);
}
unmapped_index += 1;
}
previous_segment = Some(segment);
}
if unmapped_index != self.unmapped_output_ranges.len()
|| self
.segments
.last()
.is_some_and(|segment| segment.output.end > self.output_len)
{
return Ok(false);
}
let mut previous_gap_offset: Option<usize> = None;
for gap in &self.gaps {
checkpoints.processed_item()?;
if previous_gap_offset.is_some_and(|offset| offset >= gap.output_offset) {
return Ok(false);
}
previous_gap_offset = Some(gap.output_offset);
}
let mut previous_unmapped_end: Option<usize> = None;
for range in &self.unmapped_output_ranges {
checkpoints.processed_item()?;
if previous_unmapped_end.is_some_and(|end| end > range.start) {
return Ok(false);
}
previous_unmapped_end = Some(range.end);
}
Ok(true)
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
struct EditMapSegment {
output: Range<usize>,
original: Range<usize>,
mapping: SegmentMapping,
}
impl EditMapSegment {
fn original_at_start(&self, offset: usize) -> Option<usize> {
match self.mapping {
SegmentMapping::ExactBytes => self
.original
.start
.checked_add(offset.checked_sub(self.output.start)?),
SegmentMapping::Boundaries if offset == self.output.start => Some(self.original.start),
SegmentMapping::Boundaries if offset == self.output.end => Some(self.original.end),
SegmentMapping::Boundaries => None,
SegmentMapping::Unmapped => None,
}
}
fn original_at_end(&self, offset: usize) -> Option<usize> {
self.original_at_start(offset)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum SegmentMapping {
ExactBytes,
Boundaries,
Unmapped,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct EditMapGap {
output_offset: usize,
original_left: usize,
original_right: usize,
}
#[cfg(test)]
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
struct EditMapScanStats {
copy_ranges: usize,
copy_segment_steps: usize,
copy_gap_steps: usize,
lookup_segment_advances: usize,
lookup_gap_advances: usize,
exact_segment_steps: usize,
exact_gap_steps: usize,
}
#[derive(Default)]
struct EditMapCursor {
copy_segment_index: usize,
copy_gap_index: usize,
lookup_segment_index: usize,
lookup_gap_index: usize,
exact_segment_index: usize,
exact_gap_index: usize,
#[cfg(debug_assertions)]
last_copy_end: usize,
#[cfg(debug_assertions)]
last_lookup_offset: usize,
#[cfg(debug_assertions)]
last_exact_end: usize,
#[cfg(test)]
scan_stats: EditMapScanStats,
}
impl EditMapCursor {
fn advance_lookup_to(
&mut self,
old: &SourceEditMap,
offset: usize,
checkpoints: &mut ControlledEditRebuildCheckpoints<'_>,
) -> ParseControlResult<()> {
#[cfg(debug_assertions)]
{
debug_assert!(self.last_lookup_offset <= offset);
self.last_lookup_offset = offset;
}
while old
.segments
.get(self.lookup_segment_index)
.is_some_and(|segment| segment.output.end <= offset)
{
checkpoints.processed_item()?;
self.lookup_segment_index += 1;
#[cfg(test)]
{
self.scan_stats.lookup_segment_advances += 1;
}
}
while old
.gaps
.get(self.lookup_gap_index)
.is_some_and(|gap| gap.output_offset < offset)
{
checkpoints.processed_item()?;
self.lookup_gap_index += 1;
#[cfg(test)]
{
self.scan_stats.lookup_gap_advances += 1;
}
}
Ok(())
}
fn gap_at_lookup_offset<'a>(
&self,
old: &'a SourceEditMap,
offset: usize,
) -> Option<&'a EditMapGap> {
old.gaps
.get(self.lookup_gap_index)
.filter(|gap| gap.output_offset == offset)
}
fn original_at_start(
&mut self,
old: &SourceEditMap,
offset: usize,
checkpoints: &mut ControlledEditRebuildCheckpoints<'_>,
) -> ParseControlResult<Option<usize>> {
if offset > old.output_len {
return Ok(None);
}
self.advance_lookup_to(old, offset, checkpoints)?;
if let Some(gap) = self.gap_at_lookup_offset(old, offset) {
return Ok(Some(gap.original_right));
}
if offset == old.output_len {
return Ok(match old.segments.last() {
Some(segment) => segment.original_at_end(offset),
None => Some(old.original_len),
});
}
Ok(old
.segments
.get(self.lookup_segment_index)
.filter(|segment| segment.output.start <= offset && offset < segment.output.end)
.and_then(|segment| segment.original_at_start(offset)))
}
fn original_at_end(
&mut self,
old: &SourceEditMap,
offset: usize,
checkpoints: &mut ControlledEditRebuildCheckpoints<'_>,
) -> ParseControlResult<Option<usize>> {
if offset > old.output_len {
return Ok(None);
}
self.advance_lookup_to(old, offset, checkpoints)?;
if let Some(gap) = self.gap_at_lookup_offset(old, offset) {
return Ok(Some(gap.original_left));
}
if offset == 0 {
return Ok(match old.segments.first() {
Some(segment) => segment.original_at_start(offset),
None => Some(0),
});
}
if let Some(segment) = old.segments.get(self.lookup_segment_index)
&& segment.output.start < offset
&& offset < segment.output.end
{
return Ok(segment.original_at_end(offset));
}
Ok(self
.lookup_segment_index
.checked_sub(1)
.and_then(|index| old.segments.get(index))
.filter(|segment| segment.output.start < offset && offset <= segment.output.end)
.and_then(|segment| segment.original_at_end(offset)))
}
fn original_anchor(
&mut self,
old: &SourceEditMap,
offset: usize,
checkpoints: &mut ControlledEditRebuildCheckpoints<'_>,
) -> ParseControlResult<usize> {
self.advance_lookup_to(old, offset, checkpoints)?;
if let Some(gap) = self.gap_at_lookup_offset(old, offset) {
return Ok(gap.original_right);
}
if offset == old.output_len {
return Ok(old.original_len);
}
Ok(old
.segments
.get(self.lookup_segment_index)
.filter(|segment| segment.output.start <= offset && offset < segment.output.end)
.map_or(old.original_len, |segment| segment.original.start))
}
fn range_is_exact_bytes(
&mut self,
old: &SourceEditMap,
range: &Range<usize>,
checkpoints: &mut ControlledEditRebuildCheckpoints<'_>,
) -> ParseControlResult<bool> {
#[cfg(debug_assertions)]
{
debug_assert!(self.last_exact_end <= range.start);
self.last_exact_end = range.end;
}
if range.start > range.end || range.end > old.output_len {
return Ok(false);
}
if range.start == range.end {
return Ok(true);
}
while old
.segments
.get(self.exact_segment_index)
.is_some_and(|segment| segment.output.end <= range.start)
{
checkpoints.processed_item()?;
self.exact_segment_index += 1;
#[cfg(test)]
{
self.scan_stats.exact_segment_steps += 1;
}
}
while old
.gaps
.get(self.exact_gap_index)
.is_some_and(|gap| gap.output_offset <= range.start)
{
checkpoints.processed_item()?;
self.exact_gap_index += 1;
#[cfg(test)]
{
self.scan_stats.exact_gap_steps += 1;
}
}
if old
.gaps
.get(self.exact_gap_index)
.is_some_and(|gap| gap.output_offset < range.end)
{
checkpoints.processed_item()?;
#[cfg(test)]
{
self.scan_stats.exact_gap_steps += 1;
}
return Ok(false);
}
let mut output_offset = range.start;
while output_offset < range.end {
let Some(segment) = old.segments.get(self.exact_segment_index) else {
return Ok(false);
};
checkpoints.processed_item()?;
#[cfg(test)]
{
self.scan_stats.exact_segment_steps += 1;
}
if segment.output.start > output_offset || segment.mapping != SegmentMapping::ExactBytes
{
return Ok(false);
}
output_offset = segment.output.end.min(range.end);
if segment.output.end <= range.end {
self.exact_segment_index += 1;
}
}
Ok(true)
}
}
struct EditMapBuilder {
original_len: usize,
output_len: usize,
segments: Vec<EditMapSegment>,
gaps: Vec<EditMapGap>,
cursor: EditMapCursor,
}
impl EditMapBuilder {
fn new(original_len: usize) -> Self {
Self {
original_len,
output_len: 0,
segments: Vec::new(),
gaps: Vec::new(),
cursor: EditMapCursor::default(),
}
}
fn copy_from(
&mut self,
old: &SourceEditMap,
range: Range<usize>,
checkpoints: &mut ControlledEditRebuildCheckpoints<'_>,
) -> ParseControlResult<()> {
if range.start >= range.end {
return Ok(());
}
#[cfg(debug_assertions)]
{
debug_assert!(self.cursor.last_copy_end <= range.start);
self.cursor.last_copy_end = range.end;
}
#[cfg(test)]
{
self.cursor.scan_stats.copy_ranges += 1;
}
let output_base = self.output_len;
while old
.segments
.get(self.cursor.copy_segment_index)
.is_some_and(|segment| segment.output.end <= range.start)
{
checkpoints.processed_item()?;
#[cfg(test)]
{
self.cursor.scan_stats.copy_segment_steps += 1;
}
self.cursor.copy_segment_index += 1;
}
while let Some(segment) = old.segments.get(self.cursor.copy_segment_index) {
if segment.output.start >= range.end {
break;
}
checkpoints.processed_item()?;
#[cfg(test)]
{
self.cursor.scan_stats.copy_segment_steps += 1;
}
let start = segment.output.start.max(range.start);
let end = segment.output.end.min(range.end);
debug_assert!(start < end);
let (original, mapping) = match segment.mapping {
SegmentMapping::ExactBytes => {
let original_start = segment.original.start + (start - segment.output.start);
(
original_start..original_start + (end - start),
SegmentMapping::ExactBytes,
)
}
SegmentMapping::Boundaries
if start == segment.output.start && end == segment.output.end =>
{
(segment.original.clone(), SegmentMapping::Boundaries)
}
SegmentMapping::Boundaries | SegmentMapping::Unmapped => {
let anchor = segment.original.start;
(anchor..anchor, SegmentMapping::Unmapped)
}
};
self.push_segment(EditMapSegment {
output: output_base + (start - range.start)..output_base + (end - range.start),
original,
mapping,
});
if segment.output.end <= range.end {
self.cursor.copy_segment_index += 1;
} else {
break;
}
}
while old
.gaps
.get(self.cursor.copy_gap_index)
.is_some_and(|gap| gap.output_offset < range.start)
{
checkpoints.processed_item()?;
#[cfg(test)]
{
self.cursor.scan_stats.copy_gap_steps += 1;
}
self.cursor.copy_gap_index += 1;
}
while let Some(gap) = old.gaps.get(self.cursor.copy_gap_index) {
if gap.output_offset > range.end {
break;
}
checkpoints.processed_item()?;
#[cfg(test)]
{
self.cursor.scan_stats.copy_gap_steps += 1;
}
self.push_gap(EditMapGap {
output_offset: output_base + (gap.output_offset - range.start),
original_left: gap.original_left,
original_right: gap.original_right,
});
if gap.output_offset == range.end {
break;
}
self.cursor.copy_gap_index += 1;
}
self.output_len += range.end - range.start;
Ok(())
}
fn delete_from(
&mut self,
old: &SourceEditMap,
range: Range<usize>,
checkpoints: &mut ControlledEditRebuildCheckpoints<'_>,
) -> ParseControlResult<()> {
let left = match self.cursor.original_at_end(old, range.start, checkpoints)? {
Some(offset) => offset,
None => self.cursor.original_anchor(old, range.start, checkpoints)?,
};
let right = match self.cursor.original_at_start(old, range.end, checkpoints)? {
Some(offset) => offset,
None => self.cursor.original_anchor(old, range.end, checkpoints)?,
};
self.push_gap(EditMapGap {
output_offset: self.output_len,
original_left: left,
original_right: right,
});
Ok(())
}
fn replace_from(
&mut self,
old: &SourceEditMap,
range: Range<usize>,
replacement_len: usize,
mapping: ReplacementMapping,
checkpoints: &mut ControlledEditRebuildCheckpoints<'_>,
) -> ParseControlResult<()> {
let original_start = self
.cursor
.original_at_start(old, range.start, checkpoints)?;
let start_is_mappable = original_start.is_some();
let original_start = match original_start {
Some(offset) => offset,
None => self.cursor.original_anchor(old, range.start, checkpoints)?,
};
let original_end = self.cursor.original_at_end(old, range.end, checkpoints)?;
let endpoints_are_mappable = start_is_mappable && original_end.is_some();
let original_end = original_end.unwrap_or(original_start);
let exact = mapping == ReplacementMapping::ExactBytes
&& endpoints_are_mappable
&& replacement_len == range.end - range.start
&& self.cursor.range_is_exact_bytes(old, &range, checkpoints)?
&& original_end.checked_sub(original_start) == Some(replacement_len);
self.push_segment(EditMapSegment {
output: self.output_len..self.output_len + replacement_len,
original: original_start..original_end,
mapping: if !endpoints_are_mappable {
SegmentMapping::Unmapped
} else if exact {
SegmentMapping::ExactBytes
} else {
SegmentMapping::Boundaries
},
});
self.output_len += replacement_len;
Ok(())
}
fn push_segment(&mut self, segment: EditMapSegment) {
if let Some(last) = self.segments.last_mut()
&& last.mapping == SegmentMapping::ExactBytes
&& segment.mapping == SegmentMapping::ExactBytes
&& last.output.end == segment.output.start
&& last.original.end == segment.original.start
{
last.output.end = segment.output.end;
last.original.end = segment.original.end;
return;
}
self.segments.push(segment);
}
fn push_gap(&mut self, gap: EditMapGap) {
if let Some(last) = self.gaps.last_mut() {
assert!(
last.output_offset <= gap.output_offset,
"source edit map gaps must be emitted in output order"
);
if last.output_offset == gap.output_offset {
last.original_left = last.original_left.min(gap.original_left);
last.original_right = last.original_right.max(gap.original_right);
return;
}
}
self.gaps.push(gap);
}
fn finish(
self,
output_len: usize,
checkpoints: &mut ControlledEditRebuildCheckpoints<'_>,
) -> ParseControlResult<SourceEditMap> {
debug_assert_eq!(self.output_len, output_len);
let segments = self.segments;
let mut unmapped_output_ranges = Vec::new();
for segment in &segments {
checkpoints.processed_item()?;
if segment.mapping == SegmentMapping::Unmapped {
unmapped_output_ranges.push(segment.output.clone());
}
}
Ok(SourceEditMap {
original_len: self.original_len,
output_len,
segments,
gaps: self.gaps,
unmapped_output_ranges,
#[cfg(test)]
scan_stats: self.cursor.scan_stats,
})
}
}
fn edits_are_sorted_controlled(
edits: &[SourceEdit],
checkpoints: &mut ControlledEditRebuildCheckpoints<'_>,
) -> ParseControlResult<bool> {
for pair in edits.windows(2) {
checkpoints.processed_item()?;
if (pair[0].range.start, pair[0].range.end) > (pair[1].range.start, pair[1].range.end) {
return Ok(false);
}
}
Ok(true)
}
fn assert_valid_edits_controlled(
source: &str,
edits: &[SourceEdit],
checkpoints: &mut ControlledEditRebuildCheckpoints<'_>,
) -> ParseControlResult<(usize, usize)> {
let mut cursor = 0usize;
let mut replacement_bytes = 0usize;
let mut removed_bytes = 0usize;
for edit in edits {
checkpoints.processed_item()?;
assert!(edit.range.start <= edit.range.end, "reversed source edit");
assert!(edit.range.start >= cursor, "overlapping source edits");
assert!(edit.range.end <= source.len(), "source edit out of bounds");
assert!(source.is_char_boundary(edit.range.start));
assert!(source.is_char_boundary(edit.range.end));
replacement_bytes = replacement_bytes.saturating_add(edit.replacement.len());
removed_bytes = removed_bytes.saturating_add(edit.range.end - edit.range.start);
cursor = edit.range.end;
}
Ok((replacement_bytes, removed_bytes))
}
#[cfg(test)]
mod tests {
use super::*;
use std::fmt::Write as _;
#[test]
fn composes_deletions_replacements_and_unicode_without_global_degradation() {
let original = "前A\r\nREMOVE中#quot;后";
let mut source = PreprocessedSource::new(original);
let cr = source.text().find('\r').unwrap();
source.apply_edits_uncontrolled(vec![SourceEdit::replace(
cr..cr + 2,
"\n",
ReplacementMapping::Boundaries,
)]);
let remove = source.text().find("REMOVE").unwrap();
source.apply_edits_uncontrolled(vec![SourceEdit::delete(remove..remove + "REMOVE".len())]);
let hash = source.text().find('#').unwrap();
source.apply_edits_uncontrolled(vec![
SourceEdit::replace(hash..hash + 1, "fl°", ReplacementMapping::Boundaries),
SourceEdit::replace(
hash + "#quot".len()..hash + "#quot;".len(),
"¶ß",
ReplacementMapping::Boundaries,
),
]);
assert_eq!(source.text(), "前A\n中fl°quot¶ß后");
let middle = source.text().find('中').unwrap();
let mapped = source
.try_map_span(SourceSpan::new(middle, middle + '中'.len_utf8()))
.unwrap();
assert_eq!(&original[mapped.start..mapped.end], "中");
let entity = source.text().find("fl°quot¶ß").unwrap();
let mapped = source
.try_map_span(SourceSpan::new(entity, entity + "fl°quot¶ß".len()))
.unwrap();
assert_eq!(&original[mapped.start..mapped.end], "#quot;");
let crossing_deletion = source.text().find('A').unwrap();
let after_deletion = source.text().find('中').unwrap() + '中'.len_utf8();
assert_eq!(
source.try_map_span(SourceSpan::new(crossing_deletion, after_deletion)),
None
);
}
#[test]
fn boundary_replacements_only_reject_locally_ambiguous_offsets() {
let mut source = PreprocessedSource::new("A#x;B");
source.apply_edits_uncontrolled(vec![
SourceEdit::replace(1..2, "fl°", ReplacementMapping::Boundaries),
SourceEdit::replace(3..4, "¶ß", ReplacementMapping::Boundaries),
]);
assert_eq!(source.text(), "Afl°x¶ßB");
let b = source.text().find('B').unwrap();
assert_eq!(
source.try_map_span(SourceSpan::new(b, b + 1)),
Some(SourceSpan::new(4, 5))
);
assert_eq!(source.try_map_span(SourceSpan::new(2, 2)), None);
let identity = PreprocessedSource::new("A😀B");
assert_eq!(identity.try_map_span(SourceSpan::new(2, 2)), None);
}
#[test]
fn controlled_text_rebuild_cancellation_preserves_the_previous_source_atomically() {
let original = format!(
"{}TAIL",
"a".repeat(CONTROLLED_EDIT_REBUILD_CHECKPOINT_BYTES * 2)
);
let mut source = PreprocessedSource::new(&original);
let before = source.clone();
let tail = source.text().len() - "TAIL".len();
let control = ParseControl::new();
control.cancel_after_checkpoints(1);
let result = source.apply_edits(
vec![SourceEdit::replace(
tail..tail + "TAIL".len(),
"tail",
ReplacementMapping::ExactBytes,
)],
&control,
);
assert!(result.is_err());
assert!(control.is_cancelled());
assert_source_state_eq(&source, &before);
}
#[test]
fn controlled_mapping_rebuild_cancellation_preserves_the_previous_source_atomically() {
let original = "x".repeat(CONTROLLED_EDIT_REBUILD_CHECKPOINT_ITEMS * 2);
let mut source = PreprocessedSource::new(&original);
source.apply_edits_uncontrolled(
(0..original.len())
.map(|offset| {
SourceEdit::replace(offset..offset + 1, "x", ReplacementMapping::Boundaries)
})
.collect(),
);
assert!(source.edit_map.segments.len() > CONTROLLED_EDIT_REBUILD_CHECKPOINT_ITEMS);
assert!(source.text().len() < CONTROLLED_EDIT_REBUILD_CHECKPOINT_BYTES);
let before = source.clone();
let control = ParseControl::new();
control.cancel_after_checkpoints(1);
let last_byte = source.text().len() - 1;
let result =
source.apply_edits(vec![SourceEdit::delete(last_byte..last_byte + 1)], &control);
assert!(result.is_err());
assert!(control.is_cancelled());
assert_source_state_eq(&source, &before);
}
#[test]
fn same_offset_insertions_and_adjacent_deletions_coalesce_gaps_in_order() {
let mut source = PreprocessedSource::new("aXbYc");
source.apply_edits_uncontrolled(vec![SourceEdit::delete(1..2)]);
source.apply_edits_uncontrolled(vec![
SourceEdit::replace(1..1, "<", ReplacementMapping::Boundaries),
SourceEdit::replace(1..1, ">", ReplacementMapping::Boundaries),
SourceEdit::delete(1..2),
SourceEdit::delete(2..3),
]);
assert_eq!(source.text(), "a<>c");
assert!(source.edit_map.is_well_formed());
assert_eq!(source.edit_map.gaps.len(), 2);
let c = source.text().find('c').unwrap();
assert_eq!(
source.try_map_span(SourceSpan::new(c, c + 1)),
Some(SourceSpan::new(4, 5))
);
assert_eq!(source.try_map_span(SourceSpan::new(0, c + 1)), None);
}
#[test]
fn composing_an_edit_inside_generated_text_marks_only_that_region_unmappable() {
let mut source = PreprocessedSource::new("A#x;B");
source.apply_edits_uncontrolled(vec![SourceEdit::replace(
1..2,
"fl°",
ReplacementMapping::Boundaries,
)]);
let degree = source.text().find('°').unwrap();
source.apply_edits_uncontrolled(vec![SourceEdit::replace(
degree..degree + '°'.len_utf8(),
"!",
ReplacementMapping::ExactBytes,
)]);
assert!(source.edit_map.unmapped_ranges_match_segments());
assert!(!source.edit_map.unmapped_output_ranges.is_empty());
let generated = source.text().find('fl').unwrap();
assert_eq!(
source.try_map_span(SourceSpan::new(generated, generated + 'fl'.len_utf8())),
None
);
let b = source.text().find('B').unwrap();
assert_eq!(
source.try_map_span(SourceSpan::new(b, b + 1)),
Some(SourceSpan::new(4, 5))
);
}
#[test]
fn crlf_comment_batches_scan_old_map_once_and_preserve_offsets() {
const MIN_INPUT_BYTES: usize = 1024 * 1024;
let mut original = String::with_capacity(MIN_INPUT_BYTES + 256);
let mut pair_count = 0usize;
while original.len() < MIN_INPUT_BYTES {
let group = if pair_count.is_multiple_of(2) {
"even"
} else {
"odd"
};
write!(
original,
"KEEP-{pair_count:05} payload\r\n%% {group}-comment-{pair_count:05} payload\r\n"
)
.unwrap();
pair_count += 1;
}
original.push_str("TAIL\r\n");
assert!(original.len() >= MIN_INPUT_BYTES);
let mut source = PreprocessedSource::new(&original);
source.apply_edits_uncontrolled(crlf_normalization_edits(source.text()));
assert!(!source.text().contains('\r'));
assert!(
source.edit_map.unmapped_output_ranges.is_empty(),
"CRLF boundary mappings must not make every fact lookup scan every line"
);
let even_comments = comment_line_deletions(source.text(), "%% even-comment-");
source.apply_edits_uncontrolled(even_comments);
let old_segment_count = source.edit_map.segments.len();
let old_gap_count = source.edit_map.gaps.len();
let odd_comments = comment_line_deletions(source.text(), "%% odd-comment-");
let odd_comment_count = odd_comments.len();
assert!(odd_comment_count > 8_000);
assert!(old_gap_count > 8_000);
source.apply_edits_uncontrolled(odd_comments);
let scans = source.edit_map.scan_stats;
assert_eq!(scans.copy_ranges, odd_comment_count + 1);
assert!(
scans.copy_segment_steps <= old_segment_count + scans.copy_ranges,
"copying revisited old segments: {scans:?} for {old_segment_count} segments"
);
assert!(
scans.copy_gap_steps <= old_gap_count + scans.copy_ranges,
"copying revisited old gaps: {scans:?} for {old_gap_count} gaps"
);
assert!(
scans.lookup_segment_advances <= old_segment_count,
"endpoint lookup revisited old segments: {scans:?}"
);
assert!(
scans.lookup_gap_advances <= old_gap_count,
"endpoint lookup revisited old gaps: {scans:?}"
);
assert!(!source.text().contains("%%"));
for pair_index in [0, pair_count / 2, pair_count - 1] {
let literal = format!("KEEP-{pair_index:05}");
assert_literal_mapping(&source, &original, &literal, &literal);
}
let first_keep = "KEEP-00000 payload";
let output_newline = source.text().find(first_keep).unwrap() + first_keep.len();
let original_newline = original.find(first_keep).unwrap() + first_keep.len();
assert_eq!(
source.try_map_span(SourceSpan::new(output_newline, output_newline + 1)),
Some(SourceSpan::new(original_newline, original_newline + 2))
);
let second_keep = source.text().find("KEEP-00001").unwrap();
assert_eq!(
source.try_map_span(SourceSpan::new(output_newline, second_keep + 1)),
None,
"a span crossing a removed comment must remain unmappable"
);
}
#[test]
fn seeded_edit_compositions_preserve_exact_monotonic_source_ranges() {
const SEED: u64 = 0x4d45_524d_414e_5538;
const CASES: usize = 64;
let original = "前|KEEP_A|COPY|DELETE|\r\n|#quot;|<span title=\"值😀\">|WIDE|KEEP_B|后";
let mut rng = DeterministicRng::new(SEED);
for case in 0..CASES {
let mut source = PreprocessedSource::new(original);
for transformation in shuffled_transformations(&mut rng) {
apply_transformation(&mut source, transformation);
assert_mapping_invariants(&source, original, case, transformation);
}
assert_literal_mapping(&source, original, "KEEP_A", "KEEP_A");
assert_literal_mapping(&source, original, "copy", "COPY");
assert_literal_mapping(&source, original, "\n", "\r\n");
assert_literal_mapping(
&source,
original,
"title="值😀"",
"title=\"值😀\"",
);
assert_literal_mapping(&source, original, "长值😀", "WIDE");
assert_literal_mapping(&source, original, "KEEP_B", "KEEP_B");
let crossing_start = source.text().find("copy").unwrap();
let crossing_end = source.text().find('\n').unwrap() + 1;
assert_eq!(
source.try_map_span(SourceSpan::new(crossing_start, crossing_end)),
None,
"case {case}: a span crossing deleted source must stay locally unmappable"
);
if case % 2 == 0 {
assert_literal_mapping(&source, original, "fl°quot¶ß", "#quot;");
} else {
let degree = source.text().find('°').unwrap();
source.apply_edits_uncontrolled(vec![SourceEdit::delete(
degree..degree + '°'.len_utf8(),
)]);
assert_mapping_invariants(
&source,
original,
case,
SeededTransformation::GeneratedInteriorDeletion,
);
let generated = source.text().find("flquot¶ß").unwrap();
assert_eq!(
source.try_map_span(SourceSpan::new(generated, generated + "flquot¶ß".len(),)),
None,
"case {case}: editing generated bytes must not invent an original range"
);
assert_literal_mapping(&source, original, "KEEP_B", "KEEP_B");
}
}
}
#[derive(Debug, Clone, Copy)]
enum SeededTransformation {
ExactByteReplacement,
Deletion,
CrLfNormalization,
EntityEncoding,
QuoteExpansion,
BoundaryReplacement,
GeneratedInteriorDeletion,
}
struct DeterministicRng(u64);
impl DeterministicRng {
fn new(seed: u64) -> Self {
Self(seed)
}
fn index(&mut self, upper: usize) -> usize {
self.0 ^= self.0 << 13;
self.0 ^= self.0 >> 7;
self.0 ^= self.0 << 17;
(self.0 as usize) % upper
}
}
fn shuffled_transformations(rng: &mut DeterministicRng) -> [SeededTransformation; 6] {
let mut transformations = [
SeededTransformation::ExactByteReplacement,
SeededTransformation::Deletion,
SeededTransformation::CrLfNormalization,
SeededTransformation::EntityEncoding,
SeededTransformation::QuoteExpansion,
SeededTransformation::BoundaryReplacement,
];
for index in (1..transformations.len()).rev() {
transformations.swap(index, rng.index(index + 1));
}
transformations
}
fn apply_transformation(source: &mut PreprocessedSource, transformation: SeededTransformation) {
match transformation {
SeededTransformation::ExactByteReplacement => {
replace_once(source, "COPY", "copy", ReplacementMapping::ExactBytes);
}
SeededTransformation::Deletion => {
let start = source.text().find("DELETE|").unwrap();
source.apply_edits_uncontrolled(vec![SourceEdit::delete(
start..start + "DELETE|".len(),
)]);
}
SeededTransformation::CrLfNormalization => {
replace_once(source, "\r\n", "\n", ReplacementMapping::Boundaries);
}
SeededTransformation::EntityEncoding => {
let start = source.text().find("#quot;").unwrap();
source.apply_edits_uncontrolled(vec![
SourceEdit::replace(start..start + 1, "fl°", ReplacementMapping::Boundaries),
SourceEdit::replace(
start + "#quot".len()..start + "#quot;".len(),
"¶ß",
ReplacementMapping::Boundaries,
),
]);
}
SeededTransformation::QuoteExpansion => {
let edits = source
.text()
.match_indices('"')
.map(|(start, _)| {
SourceEdit::replace(
start..start + 1,
""",
ReplacementMapping::Boundaries,
)
})
.collect();
source.apply_edits_uncontrolled(edits);
}
SeededTransformation::BoundaryReplacement => {
replace_once(source, "WIDE", "长值😀", ReplacementMapping::Boundaries);
}
SeededTransformation::GeneratedInteriorDeletion => unreachable!(),
}
}
fn replace_once(
source: &mut PreprocessedSource,
needle: &str,
replacement: &str,
mapping: ReplacementMapping,
) {
let start = source.text().find(needle).unwrap();
source.apply_edits_uncontrolled(vec![SourceEdit::replace(
start..start + needle.len(),
replacement,
mapping,
)]);
}
fn crlf_normalization_edits(text: &str) -> Vec<SourceEdit> {
text.match_indices("\r\n")
.map(|(start, _)| {
SourceEdit::replace(start..start + 2, "\n", ReplacementMapping::Boundaries)
})
.collect()
}
fn comment_line_deletions(text: &str, prefix: &str) -> Vec<SourceEdit> {
let mut line_start = 0usize;
text.split_inclusive('\n')
.filter_map(|line| {
let range = line_start..line_start + line.len();
line_start = range.end;
line.starts_with(prefix).then(|| SourceEdit::delete(range))
})
.collect()
}
fn assert_literal_mapping(
source: &PreprocessedSource,
original: &str,
output_literal: &str,
original_literal: &str,
) {
let output_start = source.text().find(output_literal).unwrap();
let original_start = original.find(original_literal).unwrap();
assert_eq!(
source.try_map_span(SourceSpan::new(
output_start,
output_start + output_literal.len(),
)),
Some(SourceSpan::new(
original_start,
original_start + original_literal.len(),
)),
"{output_literal:?} must map exactly to {original_literal:?}"
);
}
fn assert_source_state_eq(actual: &PreprocessedSource, expected: &PreprocessedSource) {
assert_eq!(actual.text, expected.text);
assert_eq!(actual.edit_map.original_len, expected.edit_map.original_len);
assert_eq!(actual.edit_map.output_len, expected.edit_map.output_len);
assert_eq!(actual.edit_map.segments, expected.edit_map.segments);
assert_eq!(actual.edit_map.gaps, expected.edit_map.gaps);
assert_eq!(
actual.edit_map.unmapped_output_ranges,
expected.edit_map.unmapped_output_ranges
);
assert_eq!(actual.edit_map.scan_stats, expected.edit_map.scan_stats);
assert_eq!(actual.global_lexemes, expected.global_lexemes);
assert_eq!(
actual.global_directive_prefixes,
expected.global_directive_prefixes
);
assert_eq!(
actual.recovered_incomplete_directive,
expected.recovered_incomplete_directive
);
}
fn assert_mapping_invariants(
source: &PreprocessedSource,
original: &str,
case: usize,
transformation: SeededTransformation,
) {
assert!(
source.edit_map.is_well_formed(),
"case {case} after {transformation:?}: malformed composed edit map"
);
assert_eq!(source.edit_map.original_len, original.len());
assert_eq!(source.edit_map.output_len, source.text().len());
let mut boundaries = source
.text()
.char_indices()
.map(|(offset, _)| offset)
.collect::<Vec<_>>();
boundaries.push(source.text().len());
let mut previous_original_offset = None;
for &offset in &boundaries {
if let Some(mapped) = source.try_map_span(SourceSpan::new(offset, offset)) {
assert_eq!(mapped.start, mapped.end);
assert!(mapped.end <= original.len());
assert!(original.is_char_boundary(mapped.start));
if let Some(previous) = previous_original_offset {
assert!(
previous <= mapped.start,
"case {case} after {transformation:?}: output boundary mapping regressed"
);
}
previous_original_offset = Some(mapped.start);
}
}
for (start_index, &start) in boundaries.iter().enumerate() {
for &end in &boundaries[start_index..] {
let Some(mapped) = source.try_map_span(SourceSpan::new(start, end)) else {
continue;
};
assert!(mapped.start <= mapped.end);
assert!(mapped.end <= original.len());
assert!(original.is_char_boundary(mapped.start));
assert!(original.is_char_boundary(mapped.end));
}
}
assert_eq!(
source.try_map_span(SourceSpan::new(0, source.text().len() + 1)),
None
);
let emoji = source.text().find('😀').unwrap();
assert_eq!(
source.try_map_span(SourceSpan::new(emoji + 1, emoji + 1)),
None
);
}
}