From 1dd18cdb4c9e537993cef42dd6bb7c040b9ca232 Mon Sep 17 00:00:00 2001 From: Micha White Date: Tue, 30 Sep 2025 11:50:13 -0400 Subject: Create pristine --- src/calculation.rs | 238 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/lib.rs | 6 +- 2 files changed, 242 insertions(+), 2 deletions(-) create mode 100644 src/calculation.rs (limited to 'src') diff --git a/src/calculation.rs b/src/calculation.rs new file mode 100644 index 0000000..e65e692 --- /dev/null +++ b/src/calculation.rs @@ -0,0 +1,238 @@ +use std::collections::{HashSet, VecDeque}; +use std::path::PathBuf; + +use crate::{FileInfo, FilenameOperation, Patch, PatchId, SpanNode, SpanNodeId}; + +fn try_retain(vec: &mut Vec, f: impl Fn(&T) -> Result) -> Result<(), E> { + let mut i = 0; + while let Some(e) = vec.get(i) { + if f(e)? { + i += 1; + } else { + vec.remove(i); + } + } + + Ok(()) +} + +fn try_any(vec: &[T], f: impl Fn(&T) -> Result) -> Result { + for e in vec { + if f(e)? { + return Ok(true); + } + } + + Ok(false) +} + +pub fn depends_on( + a: &Patch, + b: &PatchId, + get_patch: impl Fn(&PatchId) -> Result, +) -> Result { + let mut queue = VecDeque::new(); + if a.dependencies.iter().any(|id| id == b) { + return Ok(true); + } + queue.extend(a.dependencies.iter().cloned()); + + while let Some(patch_id) = queue.pop_front() { + let patch = get_patch(&patch_id)?; + if patch.dependencies.iter().any(|id| id == b) { + return Ok(true); + } + queue.extend(patch.dependencies.iter().cloned()); + } + + Ok(false) +} + +pub fn most_relevant_patches<'a, Error: Clone>( + patches: impl IntoIterator, + active_patches: &HashSet, + get_patch: &impl Fn(&PatchId) -> Result, +) -> Result, Error> { + let mut uncancelled_operations = Vec::new(); + + for patch_a in patches { + if !active_patches.contains(patch_a) { + continue; + } + + let patch_a = get_patch(patch_a)?; + try_retain(&mut uncancelled_operations, |patch_b| { + depends_on(&patch_a, patch_b, get_patch).map(|value| !value) + })?; + + if !try_any(&uncancelled_operations, |patch_b| { + depends_on(&get_patch(patch_b)?, &patch_a.id, get_patch) + })? { + uncancelled_operations.push(patch_a.id.clone()); + } + } + + Ok(uncancelled_operations) +} + +pub const fn file_name_from_operation(operation: &FilenameOperation) -> Option<&PathBuf> { + match operation { + FilenameOperation::Add { filename } | FilenameOperation::Rename { filename } => { + Some(filename) + } + FilenameOperation::Delete => None, + } +} + +pub fn file_name( + file: &FileInfo, + active_patches: &HashSet, + get_patch: &impl Fn(&PatchId) -> Result, +) -> Result>, Error> { + let most_relevant_patches = most_relevant_patches( + file.name_changes.iter().map(|(id, _)| id), + active_patches, + get_patch, + )? + .into_iter() + .collect::>(); + + Ok(file + .name_changes + .iter() + .filter(|(id, _)| most_relevant_patches.contains(id)) + .map(|(_, operation)| file_name_from_operation(operation).cloned()) + .collect()) +} + +pub struct RelevantSpanPatches { + pub additions: Vec, + pub deletions: Vec, +} + +pub fn span_liveness( + node: &SpanNode, + active_patches: &HashSet, + get_patch: &impl Fn(&PatchId) -> Result, +) -> Result { + let most_relevant_patches = most_relevant_patches( + node.added_by.iter().chain(node.deleted_by.iter()), + active_patches, + get_patch, + )? + .into_iter() + .collect::>(); + + let additions = node + .added_by + .iter() + .filter(|id| most_relevant_patches.contains(id)) + .cloned() + .collect(); + + let deletions = node + .deleted_by + .iter() + .filter(|id| most_relevant_patches.contains(id)) + .cloned() + .collect(); + + Ok(RelevantSpanPatches { + additions, + deletions, + }) +} + +pub fn conflicting_nodes( + nodes: impl Iterator, + active_patches: &HashSet, + get_patch: &impl Fn(&PatchId) -> Result, +) -> Result, Error> { + let mut conflicting_nodes = Vec::new(); + + for node in nodes { + let span_liveness = span_liveness(&node, active_patches, get_patch)?; + if !span_liveness.additions.is_empty() || !span_liveness.deletions.is_empty() { + conflicting_nodes.push(node); + } + } + + Ok(conflicting_nodes) +} + +pub struct FileContent(Vec); + +pub struct FileContentSpan(Vec); + +pub struct FileContentNode { + patch: PatchId, + content: Vec, +} + +pub fn file_content( + file: &FileInfo, + active_patches: &HashSet, + get_patch: &impl Fn(&PatchId) -> Result, +) -> Result { + let mut output = Vec::new(); + let mut completed_nodes = HashSet::new(); + + let mut queue = VecDeque::new(); + queue.push_back(file.root_span.clone()); + + let mut queue_next = VecDeque::new(); + + let mut conflicting_nodes = Vec::new(); + + while !queue.is_empty() || !queue_next.is_empty() { + while let Some(node_id) = queue.pop_front() { + let node = file + .spans + .get(&node_id) + .expect("todo: handle non-existent span-nodes"); + + let relevant_patches = span_liveness(node, active_patches, get_patch)?; + + if !node + .preceding_nodes + .iter() + .all(|id| completed_nodes.contains(id)) + { + queue.push_back(node_id); + continue; + } + + if !relevant_patches.additions.is_empty() { + let patch = get_patch(&node.span.patch)?; + let content_start = node.span.start; + let content_end = content_start + node.span.len; + let span_contents = Vec::from(&patch.contents[content_start..content_end]); + + conflicting_nodes.push(FileContentNode { + patch: node.span.patch.clone(), + content: span_contents, + }); + } + + if !relevant_patches.deletions.is_empty() { + conflicting_nodes.push(FileContentNode { + patch: node.span.patch.clone(), + content: Vec::new(), + }); + } + + completed_nodes.insert(node_id); + for node_id in &node.successor_nodes { + queue_next.push_back(node_id.clone()); + } + } + + output.push(FileContentSpan(conflicting_nodes)); + conflicting_nodes = Vec::new(); + + (queue, queue_next) = (queue_next, queue); + queue_next.clear(); + } + + Ok(FileContent(output)) +} diff --git a/src/lib.rs b/src/lib.rs index b7994d3..e854a9d 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -8,6 +8,7 @@ use std::time::Instant; use serde::{Deserialize, Serialize}; +mod calculation; mod object; mod workarea; @@ -48,9 +49,10 @@ struct Patch { id: PatchId, authors: Vec, recorder: ContributorId, + dependencies: Vec, metadata: HashMap, affected_files: Vec, - contents: String, + contents: Vec, } #[derive(Debug, Clone, Deserialize, Serialize)] @@ -58,7 +60,7 @@ struct FileInfo { id: FileId, root_span: SpanNodeId, name_changes: Vec<(PatchId, FilenameOperation)>, - spans: Vec, + spans: HashMap, } #[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)] -- cgit v1.2.3