use anyhow::{Result, anyhow};
use common::database::Store;
use common::database::rope_helpers::{BlockReplacement, block_char_length, replace_in_blocks};
use common::entities::Block;
use common::format_runs::ReplaceFormatPolicy;
use common::types::EntityId;
use std::collections::HashMap;
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) struct RangeSpec {
pub position: usize,
pub length: usize,
pub replacement: String,
}
#[derive(Debug, Clone)]
pub(crate) struct PlannedEdit {
pub block_idx: usize,
pub block_offset: usize,
pub length: usize,
pub replacement: String,
}
#[derive(Debug, Default)]
pub(crate) struct Plan {
pub edits: Vec<PlannedEdit>,
pub skipped_cross_block: i64,
pub skipped_overlapping: i64,
}
pub(crate) fn plan(blocks: &[Block], specs: &[RangeSpec], store: &Store) -> Plan {
let mut sorted: Vec<&RangeSpec> = specs.iter().collect();
sorted.sort_by_key(|s| (s.position, s.length));
let mut extents: Vec<Extent> = blocks
.iter()
.enumerate()
.map(|(block_idx, block)| Extent {
start: block.document_position.max(0) as usize,
len: block_char_length(block, store).max(0) as usize,
block_idx,
})
.collect();
extents.sort_by_key(|extent| (extent.start, extent.block_idx));
let mut sweep = 0;
let mut out = Plan::default();
let mut accepted_end: Option<usize> = None;
for spec in sorted {
if let Some(end) = accepted_end
&& spec.position < end
{
out.skipped_overlapping += 1;
continue;
}
match resolve_in_block(&extents, &mut sweep, spec.position, spec.length) {
Some((block_idx, block_offset)) => {
accepted_end = Some(spec.position + spec.length);
out.edits.push(PlannedEdit {
block_idx,
block_offset,
length: spec.length,
replacement: spec.replacement.clone(),
});
}
None => out.skipped_cross_block += 1,
}
}
out
}
#[derive(Debug, Clone, Copy)]
struct Extent {
start: usize,
len: usize,
block_idx: usize,
}
fn resolve_in_block(
extents: &[Extent],
sweep: &mut usize,
position: usize,
length: usize,
) -> Option<(usize, usize)> {
while let Some(extent) = extents.get(*sweep)
&& extent.start + extent.len < position
{
blocks_examined(1);
*sweep += 1;
}
for extent in extents.get(*sweep..).unwrap_or_default() {
blocks_examined(1);
if extent.start > position {
break;
}
let end = extent.start + extent.len;
let inside = position < end || (length == 0 && position == end);
if !inside {
continue;
}
let offset = position - extent.start;
return (offset + length <= extent.len).then_some((extent.block_idx, offset));
}
None
}
pub(crate) fn apply_plan(
store: &Store,
blocks: &[Block],
plan: &Plan,
policy: ReplaceFormatPolicy,
) -> Result<(Vec<Block>, HashMap<EntityId, i64>)> {
let mut edits: Vec<BlockReplacement<'_>> = Vec::with_capacity(plan.edits.len());
let mut delta_by_block_id: HashMap<EntityId, i64> = HashMap::new();
let mut changed: Vec<Block> = Vec::new();
for edit in &plan.edits {
let block = blocks
.get(edit.block_idx)
.ok_or_else(|| anyhow!("Block {} not found", edit.block_idx))?;
edits.push(BlockReplacement {
block,
char_start: edit.block_offset as i64,
char_end: (edit.block_offset + edit.length) as i64,
replacement: &edit.replacement,
});
let delta = delta_by_block_id.entry(block.id).or_insert_with(|| {
let mut updated = block.clone();
updated.updated_at = chrono::Utc::now();
changed.push(updated);
0
});
*delta += char_delta(edit);
}
replace_in_blocks(store, &edits, policy)?;
Ok((changed, delta_by_block_id))
}
pub(crate) fn rebase_positions(
blocks_in_order: &[Block],
delta_by_block_id: &HashMap<EntityId, i64>,
) -> (Vec<Block>, i64) {
let mut to_update = Vec::new();
let mut cumulative: i64 = 0;
for block in blocks_in_order {
if cumulative != 0 {
let mut moved = block.clone();
moved.document_position += cumulative;
moved.updated_at = chrono::Utc::now();
to_update.push(moved);
}
cumulative += delta_by_block_id.get(&block.id).copied().unwrap_or(0);
}
(to_update, cumulative)
}
pub(crate) fn char_delta(edit: &PlannedEdit) -> i64 {
edit.replacement.chars().count() as i64 - edit.length as i64
}
#[derive(Debug, Default, Clone, Copy)]
pub(crate) struct Applied {
pub replacements_count: i64,
pub skipped_cross_block: i64,
pub skipped_overlapping: i64,
}
fn blocks_examined(count: usize) {
#[cfg(test)]
tests::BLOCKS_EXAMINED.with(|examined| examined.set(examined.get() + count));
#[cfg(not(test))]
let _ = count;
}
#[cfg(test)]
mod tests {
use super::*;
use common::database::rope_helpers::{rope_append_block, rope_insert_block_boundary};
use std::cell::Cell;
thread_local! {
pub(super) static BLOCKS_EXAMINED: Cell<usize> = const { Cell::new(0) };
}
fn document(paragraphs: u64) -> (Store, Vec<Block>, Vec<RangeSpec>) {
let store = Store::new();
let mut blocks = Vec::new();
let mut specs = Vec::new();
let mut position = 0;
for id in 1..=paragraphs {
if id > 1 {
rope_insert_block_boundary(&store);
}
let text = format!("Paragraph {id} text.");
rope_append_block(&store, id, &text);
blocks.push(Block {
id,
document_position: position as i64,
..Block::default()
});
specs.push(RangeSpec {
position,
length: "Paragraph".len(),
replacement: "N".to_string(),
});
position += text.chars().count() + 1;
}
(store, blocks, specs)
}
fn examined_planning(paragraphs: u64) -> usize {
let (store, blocks, specs) = document(paragraphs);
BLOCKS_EXAMINED.with(|examined| examined.set(0));
let plan = plan(&blocks, &specs, &store);
assert_eq!(
plan.edits.len(),
paragraphs as usize,
"every range is placed"
);
assert_eq!(plan.skipped_cross_block, 0);
for (edit, block) in plan.edits.iter().zip(0..) {
assert_eq!((edit.block_idx, edit.block_offset), (block, 0));
}
BLOCKS_EXAMINED.with(Cell::get)
}
#[test]
fn placing_a_match_in_every_paragraph_looks_at_each_block_a_few_times() {
let small = examined_planning(1_000);
let large = examined_planning(2_000);
let ratio = large as f64 / small as f64;
assert!(
ratio < 2.5,
"doubling the matches from 1,000 to 2,000 made the planner look at {small} then \
{large} blocks ({ratio:.2} times): it is walking the document once per match again"
);
assert!(
large <= 3 * 2_000,
"{large} blocks looked at for 2,000 matches"
);
}
#[test]
fn ranges_are_placed_in_the_block_that_holds_them() {
let (store, blocks, _) = document(3);
let specs = vec![
RangeSpec {
position: 17,
length: 0,
replacement: "!".into(),
},
RangeSpec {
position: 17,
length: 2,
replacement: "x".into(),
},
RangeSpec {
position: 20,
length: 3,
replacement: "y".into(),
},
RangeSpec {
position: 36,
length: 0,
replacement: "z".into(),
},
];
let plan = plan(&blocks, &specs, &store);
let placed: Vec<(usize, usize)> = plan
.edits
.iter()
.map(|edit| (edit.block_idx, edit.block_offset))
.collect();
assert_eq!(placed, vec![(0, 17), (1, 2), (2, 0)]);
assert_eq!(plan.skipped_cross_block, 1);
}
}