Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_text/src/lineset.rs

5.2 KiB, 1 run

created by r1870400018:75887, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Text as a multiset of lines, for joining two copies of an append-mostly file.
2//!
3//! Written for the Daimond page log (10 Oct 2026), where two devices each appended a line to
4//! the same day's log while apart and the merge kept only one side's. A row is a non-empty
5//! line compared by its bytes, so `"a\r"` and `"a"` are two rows and a blank line is none. The
6//! k-th equal line is its own row, so a join keeps the larger count of each line and never
7//! their sum: two devices holding the same entry once hold it once after joining, while an
8//! entry made twice on purpose survives as two.
9//!
10//! The content of a join commutes and associates; its bytes do not. The bytes follow the
11//! arriving side, with the rows only here spliced in, so a join that adds nothing returns the
12//! arriving bytes exactly and repeated gossip settles.
13
14use std::collections::HashMap;
15
16
17#[derive(Clone, Debug, Default, Eq, PartialEq)]
18pub struct Joined {
19 pub bytes: Vec<u8>,
20 pub here_adds: usize, // Rows only here had
21 pub arriving_adds: usize, // Rows only arriving had
22}
23
24// One non-empty line: its bytes without the LF, and the offset just past its LF.
25#[derive(Clone, Copy, Debug)]
26struct Row<'a> {
27 text: &'a [u8],
28 next: usize,
29}
30
31fn rows(buf: &[u8]) -> Vec<Row<'_>> {
32 let mut out = Vec::new();
33 let mut start = 0;
34 while start < buf.len() {
35 let (end, next) = match buf[start..].iter().position(|b| *b == b'\n') {
36 Some(i) => (start + i, start + i + 1),
37 None => (buf.len(), buf.len()), // A torn fragment
38 };
39 if end > start {
40 out.push(Row { text: &buf[start..end], next });
41 }
42 start = next;
43 }
44 out
45}
46
47fn counts<'a>(rows: &[Row<'a>]) -> HashMap<&'a [u8], usize> {
48 let mut map = HashMap::new();
49 for row in rows {
50 *map.entry(row.text).or_insert(0) += 1;
51 }
52 map
53}
54
55// For each row, its occurrence number (1-based) and whether the other side holds that
56// occurrence too.
57fn shared<'a>(
58 rows: &[Row<'a>],
59 other: &HashMap<&'a [u8], usize>,
60)
61 -> Vec<(usize, bool)>
62{
63 let mut seen: HashMap<&[u8], usize> = HashMap::new();
64 rows.iter().map(|row| {
65 let k = seen.entry(row.text).or_insert(0);
66 *k += 1;
67 (*k, *k <= other.get(row.text).copied().unwrap_or(0))
68 }).collect()
69}
70
71/// Joins two copies of a file as multisets of lines, holding each row as many times as the
72/// side with more of it does.
73///
74/// The bytes are `arriving`'s, byte for byte when `here` has no row of its own. Otherwise each
75/// row only `here` has is placed after its nearest preceding shared row (in `here`'s order) and
76/// after the run of arriving-only rows that follows that row in `arriving`; a row with no
77/// shared row before it goes after the arriving-only rows that open `arriving`. Rows sharing a
78/// place keep `here`'s order. Each spliced row ends with LF, and an LF is added first where
79/// `arriving` ends without one.
80pub fn union_lines(arriving: &[u8], here: &[u8]) -> Joined {
81 let rows_a = rows(arriving);
82 let rows_h = rows(here);
83 let count_a = counts(&rows_a);
84 let count_h = counts(&rows_h);
85 let shared_a = shared(&rows_a, &count_h);
86 let shared_h = shared(&rows_h, &count_a);
87
88 let arriving_adds = shared_a.iter().filter(|(_, s)| !s).count();
89 let here_adds = shared_h.iter().filter(|(_, s)| !s).count();
90 if here_adds == 0 {
91 return Joined { bytes: arriving.to_vec(), here_adds, arriving_adds };
92 }
93
94 // Where each shared row sits in arriving, by (line, occurrence).
95 let mut place: HashMap<(&[u8], usize), usize> = HashMap::new();
96 for (i, row) in rows_a.iter().enumerate() {
97 if shared_a[i].1 {
98 place.insert((row.text, shared_a[i].0), i);
99 }
100 }
101 // The byte offset after the run of arriving-only rows starting at index `from`.
102 let after_run = |from: usize| -> usize {
103 let mut i = from;
104 while i < rows_a.len() && !shared_a[i].1 {
105 i += 1;
106 }
107 if i == 0 { 0 } else { rows_a[i - 1].next }
108 };
109
110 let mut splices: Vec<(usize, &[u8])> = Vec::with_capacity(here_adds);
111 let mut anchor: Option<usize> = None; // Index in arriving of the last shared row seen
112 for (j, row) in rows_h.iter().enumerate() {
113 let (k, is_shared) = shared_h[j];
114 if is_shared {
115 anchor = place.get(&(row.text, k)).copied();
116 } else {
117 let at = match anchor {
118 Some(i) => after_run(i + 1),
119 None => after_run(0),
120 };
121 splices.push((at, row.text));
122 }
123 }
124 splices.sort_by_key(|(at, _)| *at); // Stable, so here's order holds within a place
125
126 let extra: usize = splices.iter().map(|(_, t)| t.len() + 1).sum();
127 let mut bytes = Vec::with_capacity(arriving.len() + extra + 1);
128 let mut from = 0;
129 for (at, text) in splices {
130 if at > from {
131 bytes.extend_from_slice(&arriving[from..at]);
132 from = at;
133 }
134 if bytes.last().is_some_and(|b| *b != b'\n') {
135 bytes.push(b'\n');
136 }
137 bytes.extend_from_slice(text);
138 bytes.push(b'\n');
139 }
140 bytes.extend_from_slice(&arriving[from..]);
141 Joined { bytes, here_adds, arriving_adds }
142}
143
144/// The rows of `old` that `new` does not hold, by occurrence and in `old`'s order: an `old`
145/// with a line three times against a `new` with it once yields that line twice.
146pub fn missing_lines(old: &[u8], new: &[u8]) -> Vec<Vec<u8>> {
147 let rows_o = rows(old);
148 let count_n = counts(&rows(new));
149 shared(&rows_o, &count_n).into_iter()
150 .zip(rows_o.iter())
151 .filter(|((_, is_shared), _)| !is_shared)
152 .map(|(_, row)| row.text.to_vec())
153 .collect()
154}