use crate::error::Result;
use crate::etree::{TextNode, TextTree};
#[derive(Debug, Clone)]
enum Segment {
Plain(TextTree),
Region {
keyw: String,
ours_tag: RegionTag,
nodes: TextTree,
},
Atom(TextNode),
}
#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
enum RegionTag {
BeginEnd,
Encrypted,
}
fn partition(tree: &TextTree) -> Vec<Segment> {
let mut out = Vec::new();
let mut plain_buf: TextTree = Vec::new();
for node in tree {
match node {
TextNode::Plain(_) | TextNode::Data(_) => plain_buf.push(node.clone()),
TextNode::BeginEnd { keyw, txt } => {
if !plain_buf.is_empty() {
out.push(Segment::Plain(std::mem::take(&mut plain_buf)));
}
out.push(Segment::Region {
keyw: keyw.clone(),
ours_tag: RegionTag::BeginEnd,
nodes: txt.clone(),
});
}
TextNode::Encrypted {
keyw,
txt,
extfields,
} => {
if !plain_buf.is_empty() {
out.push(Segment::Plain(std::mem::take(&mut plain_buf)));
}
let _ = extfields; out.push(Segment::Region {
keyw: keyw.clone(),
ours_tag: RegionTag::Encrypted,
nodes: txt.clone(),
});
}
TextNode::Stored { .. } | TextNode::Chain { .. } | TextNode::Include { .. } => {
if !plain_buf.is_empty() {
out.push(Segment::Plain(std::mem::take(&mut plain_buf)));
}
out.push(Segment::Atom(node.clone()));
}
TextNode::Conflict { .. } => {
if !plain_buf.is_empty() {
out.push(Segment::Plain(std::mem::take(&mut plain_buf)));
}
out.push(Segment::Atom(node.clone()));
}
}
}
if !plain_buf.is_empty() {
out.push(Segment::Plain(plain_buf));
}
out
}
enum MergePick {
Take(TextTree),
Conflict {
keyw: String,
ours: TextTree,
theirs: TextTree,
},
}
enum PlainPick {
Take(TextTree),
Conflict { ours: TextTree, theirs: TextTree },
}
const PLAIN_KEYWORD: &str = "__plain__";
fn merge_one_plain(
base: Option<&TextTree>,
ours: Option<&TextTree>,
theirs: Option<&TextTree>,
) -> PlainPick {
match (base, ours, theirs) {
(Some(_), Some(o), Some(t)) if o == t => PlainPick::Take(o.clone()),
(Some(b), Some(o), Some(t)) if o == b => PlainPick::Take(t.clone()),
(Some(b), Some(o), Some(t)) if t == b => PlainPick::Take(o.clone()),
(Some(_), Some(o), Some(t)) => PlainPick::Conflict {
ours: o.clone(),
theirs: t.clone(),
},
(None, Some(o), None) => PlainPick::Take(o.clone()),
(None, None, Some(t)) => PlainPick::Take(t.clone()),
(Some(_), None, None) => PlainPick::Take(Vec::new()),
(Some(_), Some(o), None) => PlainPick::Take(o.clone()),
(Some(_), None, Some(t)) => PlainPick::Take(t.clone()),
(None, Some(o), Some(t)) if o == t => PlainPick::Take(o.clone()),
(None, Some(o), Some(t)) => PlainPick::Conflict {
ours: o.clone(),
theirs: t.clone(),
},
(None, None, None) => PlainPick::Take(Vec::new()),
}
}
pub fn merge_trees(base: &TextTree, ours: &TextTree, theirs: &TextTree) -> Result<TextTree> {
let base_seg = partition(base);
let ours_seg = partition(ours);
let theirs_seg = partition(theirs);
let find_region = |segs: &[Segment], keyw: &str, tag: RegionTag| -> Option<TextTree> {
segs.iter().find_map(|s| match s {
Segment::Region {
keyw: k,
ours_tag: t,
nodes,
} if k == keyw && *t == tag => Some(nodes.clone()),
_ => None,
})
};
let plain_at = |segs: &[Segment], i: usize| -> Option<TextTree> {
segs.iter()
.filter_map(|s| match s {
Segment::Plain(nodes) => Some(nodes.clone()),
_ => None,
})
.nth(i)
};
let mut next_plain_idx = 0usize;
let mut out: TextTree = Vec::new();
let mut handled: Vec<(String, RegionTag)> = Vec::new();
for s in &ours_seg {
match s {
Segment::Plain(nodes) => {
let i = next_plain_idx;
next_plain_idx += 1;
let base_plain = plain_at(&base_seg, i);
let theirs_plain = plain_at(&theirs_seg, i);
match merge_one_plain(base_plain.as_ref(), Some(nodes), theirs_plain.as_ref()) {
PlainPick::Take(nodes) => out.extend_from_slice(&nodes),
PlainPick::Conflict { ours, theirs } => {
out.push(TextNode::Plain("\n".to_string()));
out.push(TextNode::Conflict {
keyw: PLAIN_KEYWORD.to_string(),
ours,
theirs,
});
}
}
}
Segment::Atom(node) => out.push(node.clone()),
Segment::Region { keyw, ours_tag, .. } => {
let key = (keyw.clone(), *ours_tag);
let base_nodes = find_region(&base_seg, &key.0, key.1);
let theirs_nodes = find_region(&theirs_seg, &key.0, key.1);
let ours_nodes = find_region(&ours_seg, &key.0, key.1);
let pick = merge_one_region(
&key.0,
base_nodes.as_ref(),
ours_nodes.as_ref(),
theirs_nodes.as_ref(),
)?;
match pick {
MergePick::Take(nodes) => emit_region(&mut out, &key.0, key.1, &nodes),
MergePick::Conflict { keyw, ours, theirs } => {
out.push(TextNode::Conflict { keyw, ours, theirs });
}
}
handled.push(key);
}
}
}
for s in &theirs_seg {
if let Segment::Region { keyw, ours_tag, .. } = s {
let key = (keyw.clone(), *ours_tag);
if handled.contains(&key) {
continue;
}
let base_nodes = find_region(&base_seg, &key.0, key.1);
let theirs_nodes = find_region(&theirs_seg, &key.0, key.1);
let pick = merge_one_region(&key.0, base_nodes.as_ref(), None, theirs_nodes.as_ref())?;
match pick {
MergePick::Take(nodes) => emit_region(&mut out, &key.0, key.1, &nodes),
MergePick::Conflict { keyw, ours, theirs } => {
out.push(TextNode::Conflict { keyw, ours, theirs });
}
}
handled.push(key);
}
}
Ok(out)
}
fn merge_one_region(
keyw: &str,
base: Option<&TextTree>,
ours: Option<&TextTree>,
theirs: Option<&TextTree>,
) -> Result<MergePick> {
use Option::*;
match (base, ours, theirs) {
(Some(b), Some(o), Some(t)) if o == t && o == b => Ok(MergePick::Take(o.clone())),
(Some(_), Some(o), Some(t)) if o == t => Ok(MergePick::Take(o.clone())),
(Some(b), Some(o), Some(t)) if o != b && t == b => Ok(MergePick::Take(o.clone())),
(Some(b), Some(o), Some(t)) if t != b && o == b => Ok(MergePick::Take(t.clone())),
(Some(_), Some(o), Some(t)) => Ok(MergePick::Conflict {
keyw: keyw.to_string(),
ours: o.clone(),
theirs: t.clone(),
}),
(None, Some(o), None) => Ok(MergePick::Take(o.clone())),
(None, None, Some(t)) => Ok(MergePick::Take(t.clone())),
(Some(_), None, None) => Ok(MergePick::Take(Vec::new())),
(Some(_), Some(o), None) => Ok(MergePick::Take(o.clone())),
(Some(_), None, Some(t)) => Ok(MergePick::Take(t.clone())),
(None, Some(o), Some(t)) if o == t => Ok(MergePick::Take(o.clone())),
(None, Some(o), Some(t)) => Ok(MergePick::Conflict {
keyw: keyw.to_string(),
ours: o.clone(),
theirs: t.clone(),
}),
(None, None, None) => Ok(MergePick::Take(Vec::new())),
}
}
fn emit_region(out: &mut TextTree, keyw: &str, tag: RegionTag, nodes: &TextTree) {
if nodes.is_empty() {
return;
}
match tag {
RegionTag::BeginEnd => out.push(TextNode::BeginEnd {
keyw: keyw.to_string(),
txt: nodes.clone(),
}),
RegionTag::Encrypted => out.push(TextNode::Encrypted {
keyw: keyw.to_string(),
txt: nodes.clone(),
extfields: Default::default(),
}),
}
}
pub fn merge_paths(
base_path: &std::path::Path,
ours_path: &std::path::Path,
theirs_path: &std::path::Path,
) -> Result<usize> {
let base = read_tree(base_path)?;
let ours = read_tree(ours_path)?;
let theirs = read_tree(theirs_path)?;
let merged = merge_trees(&base, &ours, &theirs)?;
let conflicts = count_conflicts(&merged);
write_tree(ours_path, &merged)?;
Ok(conflicts)
}
fn read_tree(path: &std::path::Path) -> Result<TextTree> {
use crate::etree::ParseOps;
use std::fs::File;
use std::io::BufReader;
let f = File::open(path)?;
let mut paops = ParseOps::new(crate::crypto::default_policy())?;
paops.runtime.fname = path.display().to_string();
etree_parse(BufReader::new(f), &mut paops)
}
fn write_tree(path: &std::path::Path, tree: &TextTree) -> Result<()> {
use crate::etree::{ParseOps, tree_write};
use std::fs::File;
use std::io::BufWriter;
let f = File::create(path)?;
let mut paops = ParseOps::new(crate::crypto::default_policy())?;
paops.runtime.fname = path.display().to_string();
let mut w = BufWriter::new(f);
tree_write(&mut w, tree, &mut paops)
}
fn count_conflicts(tree: &TextTree) -> usize {
tree.iter()
.filter(|n| matches!(n, TextNode::Conflict { .. }))
.count()
}
use crate::etree as etree_parse_mod;
use etree_parse_mod::parse as etree_parse;
#[cfg(test)]
mod tests {
use super::*;
use crate::etree::{Directive, ParseOps};
use std::io::Cursor;
fn parse_str(s: &str) -> TextTree {
let mut paops = ParseOps::new(crate::crypto::default_policy()).unwrap();
crate::etree::parse(Cursor::new(s.as_bytes()), &mut paops).unwrap()
}
fn plain(s: &str) -> TextTree {
vec![TextNode::Plain(s.into())]
}
#[test]
fn identical_inputs_produce_identical_output_with_no_conflicts() {
let a = parse_str("// <( BEGIN Agent_007 )>\nhi\n// <( END Agent_007 )>\n");
let merged = merge_trees(&a, &a, &a).unwrap();
assert_eq!(merged, a);
assert_eq!(count_conflicts(&merged), 0);
}
#[test]
fn disjoint_word_changes_merge_cleanly() {
let base = parse_str(
"// <( BEGIN Agent_007 )>\nhi\n// <( END Agent_007 )>\n// <( BEGIN GEHEIM )>\nho\n// <( END GEHEIM )>\n",
);
let ours = parse_str(
"// <( BEGIN Agent_007 )>\nhi-our\n// <( END Agent_007 )>\n// <( BEGIN GEHEIM )>\nho\n// <( END GEHEIM )>\n",
);
let theirs = parse_str(
"// <( BEGIN Agent_007 )>\nhi\n// <( END Agent_007 )>\n// <( BEGIN GEHEIM )>\nho-their\n// <( END GEHEIM )>\n",
);
let merged = merge_trees(&base, &ours, &theirs).unwrap();
assert_eq!(count_conflicts(&merged), 0);
let serialized = serialize(&merged);
assert!(serialized.contains("hi-our"), "serialized = {serialized}");
assert!(serialized.contains("ho-their"));
}
#[test]
fn same_word_different_content_produces_conflict() {
let base = parse_str("// <( BEGIN Agent_007 )>\nhi\n// <( END Agent_007 )>\n");
let ours = parse_str("// <( BEGIN Agent_007 )>\nhi-our\n// <( END Agent_007 )>\n");
let theirs = parse_str("// <( BEGIN Agent_007 )>\nhi-their\n// <( END Agent_007 )>\n");
let merged = merge_trees(&base, &ours, &theirs).unwrap();
assert_eq!(count_conflicts(&merged), 1);
match &merged[0] {
TextNode::Conflict { keyw, ours, theirs } => {
assert_eq!(keyw, "Agent_007");
assert!(!ours.is_empty());
assert!(!theirs.is_empty());
}
other => panic!("expected Conflict, got {other:?}"),
}
}
#[test]
fn one_sided_delete_against_modify_keeps_modify() {
let base = parse_str("// <( BEGIN X )>\nbody\n// <( END X )>\n");
let ours = parse_str("// <( BEGIN X )>\nbody-modified\n// <( END X )>\n");
let theirs = parse_str("plain trailing line\n");
let merged = merge_trees(&base, &ours, &theirs).unwrap();
assert_eq!(count_conflicts(&merged), 0);
let serialized = serialize(&merged);
assert!(serialized.contains("body-modified"));
}
#[test]
fn both_sides_modified_plain_emits_plain_conflict() {
let base = parse_str("intro\n// <( BEGIN X )>\nbody\n// <( END X )>\n");
let ours = parse_str("intro-our\n// <( BEGIN X )>\nbody\n// <( END X )>\n");
let theirs = parse_str("intro-their\n// <( BEGIN X )>\nbody\n// <( END X )>\n");
let merged = merge_trees(&base, &ours, &theirs).unwrap();
let serialized = serialize(&merged);
assert!(
serialized.contains("CONFLICT __plain__"),
"expected __plain__ conflict; got:\n{serialized}"
);
assert!(serialized.contains("intro-our"));
assert!(serialized.contains("intro-their"));
}
#[test]
fn one_sided_plain_change_merges_cleanly() {
let base = parse_str("intro\n// <( BEGIN X )>\nbody\n// <( END X )>\n");
let ours = parse_str("intro-our\n// <( BEGIN X )>\nbody\n// <( END X )>\n");
let theirs = parse_str("intro\n// <( BEGIN X )>\nbody\n// <( END X )>\n");
let merged = merge_trees(&base, &ours, &theirs).unwrap();
assert_eq!(count_conflicts(&merged), 0);
assert!(serialize(&merged).contains("intro-our"));
}
#[test]
fn identical_plain_change_on_both_sides_merges_cleanly() {
let base = parse_str("intro\n// <( BEGIN X )>\nbody\n// <( END X )>\n");
let ours = parse_str("intro-edited\n// <( BEGIN X )>\nbody\n// <( END X )>\n");
let theirs = parse_str("intro-edited\n// <( BEGIN X )>\nbody\n// <( END X )>\n");
let merged = merge_trees(&base, &ours, &theirs).unwrap();
assert_eq!(count_conflicts(&merged), 0);
}
fn serialize(tree: &TextTree) -> String {
let mut buf: Vec<u8> = Vec::new();
let mut paops = ParseOps::new(crate::crypto::default_policy()).unwrap();
crate::etree::tree_write(&mut buf, tree, &mut paops).unwrap();
String::from_utf8(buf).unwrap()
}
#[test]
fn round_trips_through_partition() {
let a =
parse_str("leading\n// <( BEGIN Agent_007 )>\nhi\n// <( END Agent_007 )>\ntrailing\n");
let merged = merge_trees(&a, &a, &a).unwrap();
let s = serialize(&merged);
assert!(s.contains("leading"));
assert!(s.contains("trailing"));
assert!(s.contains("Agent_007"));
let _ = Directive::Begin; }
#[test]
#[allow(dead_code)]
fn plain_helper_compiles() {
let _ = plain("hello");
}
}