Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_text/tests/lineset.rs

9.4 KiB, 1 run

created by r1870400018:75889, 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//! `lineset::union_lines` and `lineset::missing_lines`: a file as a multiset of lines.
2//!
3//! Written for the Daimond page log (10 Oct 2026). On 7 Oct two devices each appended one row
4//! to the same diet log while apart, and the merge kept one side's. The first case is that
5//! shape, with synthetic rows.
6
7use oxedyne_fe2o3_text::lineset::{
8 missing_lines,
9 union_lines,
10 Joined,
11};
12
13use std::collections::BTreeMap;
14
15
16// The rows of a buffer as a multiset.
17fn content(buf: &[u8]) -> BTreeMap<Vec<u8>, usize> {
18 let mut map = BTreeMap::new();
19 for line in buf.split(|b| *b == b'\n') {
20 if !line.is_empty() {
21 *map.entry(line.to_vec()).or_insert(0) += 1;
22 }
23 }
24 map
25}
26
27fn max_of(a: &BTreeMap<Vec<u8>, usize>, b: &BTreeMap<Vec<u8>, usize>) -> BTreeMap<Vec<u8>, usize> {
28 let mut out = a.clone();
29 for (k, n) in b {
30 let e = out.entry(k.clone()).or_insert(0);
31 *e = (*e).max(*n);
32 }
33 out
34}
35
36fn join(arriving: &str, here: &str) -> Joined {
37 union_lines(arriving.as_bytes(), here.as_bytes())
38}
39
40fn text(j: &Joined) -> String {
41 String::from_utf8_lossy(&j.bytes).into_owned()
42}
43
44struct XorShift(u64);
45
46impl XorShift {
47 fn next(&mut self) -> u64 {
48 let mut x = self.0;
49 x ^= x << 13;
50 x ^= x >> 7;
51 x ^= x << 17;
52 self.0 = x;
53 x
54 }
55 fn below(&mut self, n: u64) -> u64 {
56 self.next() % n
57 }
58}
59
60// A small vocabulary, so rows collide and repeat often.
61const WORDS: [&[u8]; 7] = [b"a", b"b", b"c", b"a\r", b"a ", b"\xff\xfe", b"{\"id\":\"q\"}"];
62
63fn random_file(rng: &mut XorShift) -> Vec<u8> {
64 let mut out = Vec::new();
65 let n = rng.below(7);
66 for _ in 0..n {
67 match rng.below(9) {
68 0 => out.push(b'\n'), // A blank line
69 _ => {
70 out.extend_from_slice(WORDS[rng.below(WORDS.len() as u64) as usize]);
71 out.push(b'\n');
72 }
73 }
74 }
75 if !out.is_empty() && rng.below(4) == 0 {
76 out.pop(); // No final newline, or a torn last row
77 }
78 out
79}
80
81#[test]
82fn seven_oct_both_kept() {
83 let shared = concat!(
84 "{\"id\":\"t0brekfst001\",\"at\":\"2026-10-07T07:40:12+08:00\",\"day\":\"2026-10-07\",\"src\":\"scale\",\"f\":{\"food\":\"toast\",\"qty\":1},\"w\":1000000000001}\n",
85 "{\"id\":\"t0coffee0002\",\"at\":\"2026-10-07T08:02:47+08:00\",\"day\":\"2026-10-07\",\"src\":\"chat\",\"f\":{\"food\":\"coffee\",\"qty\":1},\"w\":1000000000002}\n",
86 );
87 let oats = "{\"id\":\"t0oats000003\",\"at\":\"2026-10-07T11:06:05+08:00\",\"day\":\"2026-10-07\",\"src\":\"scale\",\"f\":{\"food\":\"oats\",\"qty\":1},\"w\":1000000000003}\n";
88 let eggs = "{\"id\":\"t0eggs000004\",\"at\":\"2026-10-07T11:15:55+08:00\",\"day\":\"2026-10-07\",\"src\":\"scale\",\"f\":{\"food\":\"egg\",\"qty\":2},\"w\":1000000000004}\n";
89 let arriving = format!("{}{}", shared, oats);
90 let here = format!("{}{}", shared, eggs);
91 let j = join(&arriving, &here);
92 assert_eq!(text(&j), format!("{}{}{}", shared, oats, eggs));
93 assert_eq!((j.here_adds, j.arriving_adds), (1, 1));
94 // From the other side, both rows are still kept.
95 let k = join(&here, &arriving);
96 assert_eq!(text(&k), format!("{}{}{}", shared, eggs, oats));
97 assert_eq!((k.here_adds, k.arriving_adds), (1, 1));
98}
99
100#[test]
101fn duplicates_by_occurrence() {
102 let j = join("x\nx\n", "x\n");
103 assert_eq!((text(&j).as_str(), j.here_adds, j.arriving_adds), ("x\nx\n", 0, 1));
104 let j = join("x\n", "x\nx\n");
105 assert_eq!((text(&j).as_str(), j.here_adds, j.arriving_adds), ("x\nx\n", 1, 0));
106 let j = join("x\n", "x\nx\nx\n");
107 assert_eq!((text(&j).as_str(), j.here_adds, j.arriving_adds), ("x\nx\nx\n", 2, 0));
108 let j = join("x\nx\nx\n", "x\n");
109 assert_eq!((text(&j).as_str(), j.here_adds, j.arriving_adds), ("x\nx\nx\n", 0, 2));
110 let j = join("x\nx\n", "x\nx\n");
111 assert_eq!((text(&j).as_str(), j.here_adds, j.arriving_adds), ("x\nx\n", 0, 0));
112}
113
114#[test]
115fn settles_bytes() {
116 for (arriving, here) in [
117 ("b\na\nc\n", "a\nc\n"),
118 ("b\na\nc", "c\na\n"), // Order and the final newline do not matter
119 ("\n\na\n\nb\n", "b\n\n"),
120 ("a\nb\n", ""),
121 ("a\r\nb \n", "b \na\r\n"),
122 ] {
123 let j = join(arriving, here);
124 assert_eq!(j.bytes, arriving.as_bytes(), "{:?} against {:?}", arriving, here);
125 assert_eq!(j.here_adds, 0);
126 }
127}
128
129#[test]
130fn content_commutative_associative() {
131 let mut rng = XorShift(0x9E37_79B9_7F4A_7C15);
132 for _ in 0..20_000 {
133 let a = random_file(&mut rng);
134 let b = random_file(&mut rng);
135 let c = random_file(&mut rng);
136 let (ca, cb, cc) = (content(&a), content(&b), content(&c));
137
138 let ab = union_lines(&a, &b);
139 let ba = union_lines(&b, &a);
140 let want = max_of(&ca, &cb);
141 assert_eq!(content(&ab.bytes), want, "a={:?} b={:?}", a, b);
142 assert_eq!(content(&ba.bytes), want, "a={:?} b={:?}", a, b);
143 let only_b: usize = cb.iter().map(|(k, n)| n.saturating_sub(*ca.get(k).unwrap_or(&0))).sum();
144 let only_a: usize = ca.iter().map(|(k, n)| n.saturating_sub(*cb.get(k).unwrap_or(&0))).sum();
145 assert_eq!((ab.here_adds, ab.arriving_adds), (only_b, only_a));
146
147 let left = union_lines(&ab.bytes, &c);
148 let bc = union_lines(&b, &c);
149 let right = union_lines(&a, &bc.bytes);
150 let want3 = max_of(&want, &cc);
151 assert_eq!(content(&left.bytes), want3);
152 assert_eq!(content(&right.bytes), want3);
153 }
154}
155
156#[test]
157fn idempotent_bytes() {
158 let mut rng = XorShift(0x0123_4567_89AB_CDEF);
159 for _ in 0..5_000 {
160 let a = random_file(&mut rng);
161 let h = random_file(&mut rng);
162 let aa = union_lines(&a, &a);
163 assert_eq!(aa.bytes, a);
164 assert_eq!((aa.here_adds, aa.arriving_adds), (0, 0));
165 let once = union_lines(&a, &h);
166 let twice = union_lines(&once.bytes, &h);
167 assert_eq!(twice.bytes, once.bytes, "a={:?} h={:?}", a, h);
168 assert_eq!(twice.here_adds, 0);
169 }
170}
171
172#[test]
173fn three_device_gossip_converges() {
174 let mut rng = XorShift(0xDEAD_BEEF_CAFE_F00D);
175 for _ in 0..2_000 {
176 let mut dev = [random_file(&mut rng), random_file(&mut rng), random_file(&mut rng)];
177 let want = max_of(&max_of(&content(&dev[0]), &content(&dev[1])), &content(&dev[2]));
178 let mut rounds = 0;
179 loop {
180 let mut changed = false;
181 for i in 0..3 {
182 for j in 0..3 {
183 if i != j {
184 let next = union_lines(&dev[j], &dev[i]).bytes; // i pulls from j
185 if next != dev[i] {
186 dev[i] = next;
187 changed = true;
188 }
189 }
190 }
191 }
192 rounds += 1;
193 if !changed {
194 break;
195 }
196 assert!(rounds < 6, "no fixpoint after {} rounds: {:?}", rounds, dev);
197 }
198 assert_eq!(dev[0], dev[1]);
199 assert_eq!(dev[1], dev[2]);
200 assert_eq!(content(&dev[0]), want);
201 }
202}
203
204#[test]
205fn r4_order() {
206 for (arriving, here, want) in [
207 // After the nearest preceding shared row, past arriving's own rows after it.
208 ("s1\na1\ns2\n", "s1\nh1\ns2\n", "s1\na1\nh1\ns2\n"),
209 // No shared row before: after the arriving-only rows that open arriving.
210 ("a0\ns1\n", "h0\ns1\n", "a0\nh0\ns1\n"),
211 ("s1\n", "h0\ns1\n", "h0\ns1\n"),
212 // The anchor is arriving's last row.
213 ("s1\na1\n", "s1\nh1\n", "s1\na1\nh1\n"),
214 // Several here rows in one place keep here's order.
215 ("s1\ns2\n", "s1\nh1\nh2\ns2\nh3\n", "s1\nh1\nh2\ns2\nh3\n"),
216 // The anchor is found in arriving wherever it sits there.
217 ("s2\ns1\n", "s1\nh1\ns2\n", "s2\ns1\nh1\n"),
218 // The anchor is a row by occurrence: here's second x is arriving's second x.
219 ("x\na\nx\n", "x\nx\nh\n", "x\na\nx\nh\n"),
220 // Blank lines after the run stay after the spliced rows.
221 ("s1\n\ns2\n", "s1\nh\ns2\n", "s1\nh\n\ns2\n"),
222 ] {
223 let j = join(arriving, here);
224 assert_eq!(text(&j), want, "{:?} against {:?}", arriving, here);
225 }
226}
227
228#[test]
229fn byte_exact() {
230 let j = join("a\r\n", "a\n");
231 assert_eq!((text(&j).as_str(), j.here_adds, j.arriving_adds), ("a\r\na\n", 1, 1));
232 let j = join("a \n", "a\n");
233 assert_eq!((text(&j).as_str(), j.here_adds, j.arriving_adds), ("a \na\n", 1, 1));
234 let j = union_lines(b"\xff\xfe\n", b"\xff\n");
235 assert_eq!(j.bytes, b"\xff\xfe\n\xff\n".to_vec());
236 let j = union_lines(b"\xff\n", b"\xff\n");
237 assert_eq!((j.bytes, j.here_adds), (b"\xff\n".to_vec(), 0));
238}
239
240#[test]
241fn newline_edges() {
242 let j = join("", "");
243 assert_eq!((text(&j).as_str(), j.here_adds, j.arriving_adds), ("", 0, 0));
244 let j = join("", "x");
245 assert_eq!((text(&j).as_str(), j.here_adds), ("x\n", 1));
246 let j = join("x", "");
247 assert_eq!((text(&j).as_str(), j.arriving_adds), ("x", 1));
248 // Arriving lacks a final newline, so one is added before the spliced row.
249 let j = join("a", "b\n");
250 assert_eq!(text(&j), "a\nb\n");
251 // Blank lines are never rows: never spliced, and arriving's kept as they are.
252 let j = join("a\n", "\n\na\n\n");
253 assert_eq!((text(&j).as_str(), j.here_adds), ("a\n", 0));
254 let j = join("\n\n", "x\n");
255 assert_eq!((text(&j).as_str(), j.here_adds, j.arriving_adds), ("x\n\n\n", 1, 0));
256 let j = join("a\n\n\n", "a\nb\n");
257 assert_eq!(text(&j), "a\nb\n\n\n");
258}
259
260#[test]
261fn torn_fragment_is_a_row() {
262 // A fragment equal to a whole row is that row.
263 let j = join("a\nb", "a\nb\n");
264 assert_eq!((text(&j).as_str(), j.here_adds), ("a\nb", 0));
265 // A fragment unequal to any row is a row of its own, on either side.
266 let j = join("a\n", "a\nbro");
267 assert_eq!((text(&j).as_str(), j.here_adds), ("a\nbro\n", 1));
268 let j = join("a\nbro", "a\nbrown\n");
269 assert_eq!((text(&j).as_str(), j.here_adds, j.arriving_adds), ("a\nbro\nbrown\n", 1, 1));
270}
271
272#[test]
273fn missing_lines_by_occurrence() {
274 let lost = missing_lines(b"x\ny\nx\nx\n", b"x\n");
275 assert_eq!(lost, vec![b"y".to_vec(), b"x".to_vec(), b"x".to_vec()]);
276 assert!(missing_lines(b"x\nx\n", b"x\nx\nx\n").is_empty());
277 assert!(missing_lines(b"\n\n\n", b"").is_empty()); // Blank lines are not rows
278 assert_eq!(missing_lines(b"a\r\n", b"a\n"), vec![b"a\r".to_vec()]);
279 assert_eq!(missing_lines(b"a\nfrag", b"a\n"), vec![b"frag".to_vec()]);
280 assert!(missing_lines(b"", b"a\n").is_empty());
281}